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

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

2933번: 미네랄

이 문제에서 구현할 건 크게 두 가지.

 

1. 막대기로 미네랄 깨기

 

2. 클러스터 내리기

 

여기서 2가 상당히 복잡합니다.

여기서 클러스터라는 게 빡셉니다.

문제를 잘 읽어보면

클러스터는 한 덩어리입니다.

그래서 미네랄 하나만 내리는 것과 비교하면

많이 복잡한 편입니다.

그림으로 예시를 구현해봤습니다.

저렇게 한 덩이가 그대로 내려와야합니다.

그리고 저 내려오는 걸 구현하는 게 상당히 난해했습니다.

https://chelseashin.tistory.com/88

[BOJ] 2933. 미네랄(Python) / Simulation + BFS

제 나름대로 구현해보다가

아이디어가 필요해서 참고한 코드.

여기서 작성한 방식은

 

1. 먼저 땅과 붙어있는 클러스터를 구한다

(땅과 붙어있는 쪽은 떨어지지 않는다)

 

2. 막대가 미네랄을 부순 좌표기준으로

상하좌우를 보고 클러스터 탐색

(이 때, 땅과 붙어있는 클러스터는 제외)

 

3. 클러스터에서 가장 아랫쪽에 있는 걸 기준으로

최대로 내려갈 수 있는 걸 카운트하고

내려보낸다

 

#백준 2933번 미네랄
from collections import deque

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


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


#0,2,4,6...-->왼쪽
#1,3,5,7...->오른쪽

for i in range(N):
    #1 던지기
    bomb=False
    if i%2==0:
        start_x=R-throw[i]
        start_y=0
        #왼쪽에서 오른쪽으로 던지기
        while start_y<C:
            if room[start_x][start_y]=="x":
                room[start_x][start_y]="."
                bx=start_x
                by=start_y
                bomb=True
                break
            start_y+=1


    else:
        start_x=R-throw[i]
        start_y=C-1
        #오른쪽에서 왼쪽으로 던지기
        while start_y>=0:
            if room[start_x][start_y]=="x":
                room[start_x][start_y]="."
                bx=start_x
                by=start_y
                bomb=True
                break
            start_y-=1

    #2 땅에 붙어있는 미네랄 체크
    if bomb==False:
        continue
    cluster=[]
    fall=[]
    visited=[[0]*C for _ in range(R)]
    for y in range(C):
        if room[R-1][y]=="x" and not visited[R-1][y]:
            visited[R-1][y]=1
            q=deque()
            q.append([R-1,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]:
                        continue
                    if room[nx][ny]==".":
                        continue

                    q.append([nx,ny])
                    visited[nx][ny]=1
    #3 공중에 있는 클러스터
    for d in range(4):
        px=bx+dx[d]
        py=by+dy[d]

        if px < 0 or px >= R or py < 0 or py >= C:
            continue
        if visited[px][py]:
            continue
        if room[px][py] == '.':
            continue
        visited[px][py]=2
        q=deque()
        q.append([px,py])
        cluster.append([px,py])
        room[px][py]="."
        while q:
            px, py = q.popleft()
            if room[px + 1][py] == ".":
                fall.append([px, py])
            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]:
                    continue
                if room[nx][ny] == ".":
                    continue

                q.append([nx, ny])
                visited[nx][ny] = 2
                cluster.append([nx,ny])
                room[nx][ny]='.'
    #4 최대 내려갈 수 있는 숫자 구하기
    if fall:
        under=False
        down=1
        while True:
            for x, y in fall:
                if x + down >= R-1:
                    under = True
                    break
                if room[x + down+1][y] == "x" and visited[x+down+1][y]:
                    under = True
                    break
            if under==True:
                break
            down+=1
        #5 내려가주기
        for nx,ny in cluster:
            room[nx+down][ny]="x"
for row in room:
    print(''.join(row))

저는 이 문제에서 구현까지는 다 되다가

마지막 #5에서 조금 에러가 났습니다.

for x, y in cluster:

라고 했던 걸

for nx,ny in cluster:

라고 바꿔야지

통과가 되더군요.

위에대로 해도 예시는 통과가 되던데

채점은 틀렸다고 떴습니다.

아마 위에 #4와 변수가 겹쳐서

프로그램을 돌릴 때 혼동이 온 것이라고 생각이 듭니다.