[백준 18500번] 미네랄2(파이썬)

https://www.acmicpc.net/problem/18500

18500번: 미네랄 2

2022.08.18 - [알고리즘 공부] - [백준 2933번] 미네랄(파이썬)

[백준 2933번] 미네랄(파이썬)

위의 문제와 완전 똑같습니다.

그런데...

위의 코드 정답으로 제출하면

틀렸다고 뜰 것입니다.

https://www.acmicpc.net/board/view/92636

글 읽기 - 미네랄1과 다른 반례들 모음

질문글을 보면

'클러스터의 모든 지점을 다 확인해야한다'

라는 것.

미네랄1은

'바닥만 확인'하면 되겠지만

미네랄2는 다른 것도 봐야합니다.

그림을 보면 이해가 되실 겁니다.

제출후에 알았지만

저같은 경우에는 미네랄1에서 제출했던 코드로도

미네랄 2를 제출해도 맞긴 했습니다.

하지만 만약에

미네랄 1을 풀었을 때

'바닥'만 떨어지는 걸로 구했다면

미네랄2에서는 다시 풀어야합니다.

 

#백준 18500번 미네랄2
from collections import deque
R,C=map(int,input().split())

room=[]
for _ in range(R):
    tmp=list(input().rstrip())
    room.append(tmp)
N=int(input())
throw=list(map(int,input().split()))

dx=[0,0,1,-1]
dy=[1,-1,0,0]


#i가 짝수->왼쪽
#i가 홀수->오른쪽

for i in range(N):
    now_throw=R-throw[i]
    b_f=False
    #왼쪽던짐
    if i%2==0:
        nx=now_throw
        ny=0
        while ny<C:
            if room[nx][ny]=='x':
                b_f=True
                break
            ny+=1
        if b_f:
            room[nx][ny]='.'
    #오른쪽 던짐
    else:
        nx = now_throw
        ny = C-1
        #하...범위때문에 개고생했다....하...범위 잘보자...하.....
        while ny >=0:
            if room[nx][ny] == 'x':
                b_f = True
                break
            ny -= 1

        if b_f:
            room[nx][ny] = '.'

    #클러스터 하강
    visited = [[-1] * C for _ in range(R)]
    cluster=[]
    cnt=0
    #먼저 클러스터 구역보기
    for x in range(R):
        for y in range(C):
            if room[x][y]=='x' and visited[x][y]==-1:
                tmp=[]
                q=deque()
                q.append([x,y])
                visited[x][y]=cnt
                tmp.append([x,y])
                while q:

                    px,py=q.popleft()

                    for d in range(4):
                        nx=px+dx[d]
                        ny=py+dy[d]

                        if nx<0 or nx>=R or ny<0 or ny>=C:
                            continue
                        if visited[nx][ny]!=-1:
                            continue
                        if room[nx][ny]=='.':
                            continue

                        q.append([nx,ny])
                        visited[nx][ny]=cnt
                        tmp.append([nx,ny])

                tmp.sort(reverse=True)
                cluster.append(tmp)
                cnt+=1
    #클러스터 바닥부터 다운

    for k in range(cnt):
        clu=cluster[k]
        n_cnt=k
        c_b=clu[0][0]
        #바닥이 땅에 붙은 클러스터는 굳이 할 필요없다.
        if c_b==R-1:
            continue

        fall=1
        #얼마나 내려갈 수 있는지 본다
        while True:
            flag=False
            for x,y in clu:
                nx=x+fall
                if nx>=R:
                    flag=True
                    break
                if room[nx][y]=='x' and visited[nx][y]!=n_cnt:
                    flag=True
                    break
            if flag:
                fall-=1
                break
            fall+=1

        #그 다음 하강
        for x,y in clu:
            room[x][y]='.'
            room[x+fall][y]='x'


for row in room:
    print(''.join(row))

 

코드는 미네랄1과 좀 다르게 풀었습니다.

범위때문에...진짜 한시간을 고생했네요.

분명 반례 다 통과하길래.

욕하면서 이게 뭐지?

로직 다 맞는데

진짜 억까 개심하다...

이게 프로그래밍인가...

이건 아니지.

이런 넉두리를 무한반복.

결국 예제 코드로 강제정답입력하고

(c++코드)

파이썬 코드를 찾아봐도

아니! 내 코드랑 뭐가 다른데스요?

하다가...

 

미네랄1과 비교하다가

어라?

범위가 하나 틀렸...

하............

 

하긴 제출할 떄 계속 8%에서 막혔는데

범위를 생각해봄직했어야지 바부야.

하...범위체크 잘하자.