[골드 1] 백준 2933 - 미네랄 (파이썬)

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

풀이

• 막대기를 던져 미네랄(‘x’)을 부수면, 공중에 뜬 미네랄 클러스터는 중력 방향으로 낙하해야 한다.
• 미네랄은 바닥 또는 다른 미네랄과 맞닿아 있어야 멈춘다.
• 막대기는 번갈아 가며 왼쪽/오른쪽에서 날아오며, 부딪힌 첫 번째 미네랄을 부순다.

1. 막대기 던지기

• 입력받은 높이에 따라 해당 줄에서 가장 먼저 만나는 미네랄(‘x’)을 제거한다.
• 던지는 방향은 짝수 턴에는 왼쪽에서 오른쪽, 홀수 턴에는 오른쪽에서 왼쪽이다.

2. 클러스터 탐색 (BFS)

• 미네랄 덩어리(클러스터)는 상하좌우 인접한 미네랄끼리 연결되어 있다.
• visited 배열을 이용해 미네랄 덩어리를 하나씩 탐색한다.

3. 공중 클러스터 분리 및 낙하 처리

• 바닥에 닿지 않은 클러스터는 중력의 영향을 받는다.
• 해당 클러스터가 얼마나 아래로 내려갈 수 있는지 계산하고, 해당 거리만큼 미네랄을 아래로 이동시킨다.

from collections import deque

R, C = map(int, input().split())          # 미네랄 필드의 행(R), 열(C)
B = [list(input()) for _ in range(R)]     # 미네랄 필드 상태
N = int(input())                          # 막대기 던지는 횟수
H = list(map(int, input().split()))       # 각 턴마다 막대기가 던져지는 높이

# 상, 하, 좌, 우 방향 벡터
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

• B[r][c] == 'x' : 미네랄
• B[r][c] == '.' : 빈 공간
• H[i]는 위에서부터가 아닌 아래에서 i번째 줄을 의미하므로, 내부 계산은 R - H[i].

def throw(turn, height):
    row = R - height  # 맨 아래가 0번 인덱스가 아님에 유의

    # 왼쪽 → 오른쪽 (짝수턴)
    if turn % 2 == 0:
        for col in range(C):
            if B[row][col] == "x":
                B[row][col] = "."
                break
    # 오른쪽 → 왼쪽 (홀수턴)
    else:
        for col in range(C - 1, -1, -1):
            if B[row][col] == "x":
                B[row][col] = "."
                break

• 현재 턴의 방향에 따라 가장 먼저 만나는 미네랄을 파괴한다.
• 주의: 딱 하나만 부수고 멈추는 게 핵심!

def bfs(r, c, visited):
    queue = deque()
    queue.append((r, c))
    visited[r][c] = True
    cluster = [(r, c)]  # 현재 클러스터에 포함된 좌표들

    while queue:
        r, c = queue.popleft()
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]
            if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and B[nr][nc] == 'x':
                visited[nr][nc] = True
                queue.append((nr, nc))
                cluster.append((nr, nc))

    return cluster

• 주어진 시작점에서 연결된 모든 미네랄 좌표를 리스트로 반환.
• 상하좌우 탐색으로 연결된 'x'만 탐색.
• visited를 사용하여 중복 탐색 방지.

def drop(cluster):
    cluster_set = set(cluster)            # O(1) 탐색용 집합
    cluster.sort(reverse=True)            # 아래에 있는 좌표부터 지우기 위해

    # 원래 있던 위치를 빈칸으로
    for r, c in cluster:
        B[r][c] = '.'

    min_fall = R
    for r, c in cluster:
        fall = 0
        nr = r + 1
        while nr < R and B[nr][c] == '.' and (nr, c) not in cluster_set:
            fall += 1
            nr += 1
        min_fall = min(min_fall, fall)

    # 새로운 위치에 다시 미네랄 넣기
    for r, c in cluster:
        B[r + min_fall][c] = 'x'

• 공중에 떠 있는 미네랄을 지우고, 얼마나 아래로 떨어질 수 있는지 계산한 뒤, 다시 그 위치에 미네랄을 채워 넣음.
• cluster.sort(reverse=True)는 먼저 아래에 있는 미네랄부터 비워야 충돌 방지 가능.

for i in range(N):
    throw(i, H[i])  # 막대기 던짐

    visited = [[False] * C for _ in range(R)]
    for r in range(R - 1, -1, -1):  # 아래부터 스캔 (공중 클러스터 우선 탐색)
        for c in range(C):
            if B[r][c] == 'x' and not visited[r][c]:
                cluster = bfs(r, c, visited)
                is_ground = any(r == R - 1 for r, _ in cluster)
                if not is_ground:  # 공중에 떠 있으면 낙하 처리
                    drop(cluster)
                    break
        else:
            continue
        break

• 각 턴마다:
  1. 막대기 던짐 → 미네랄 제거
  2. BFS로 클러스터 탐색
  3. 공중에 떠 있는 클러스터가 있으면 하나만 낙하시킴
• break 2개로 감싼 이유는 한 번에 하나의 클러스터만 떨어뜨리기 위해서임.

# 백준 2933 - 미네랄
# 분류 : BFS
# 문제집 : 단기간 성장 - 6번

from collections import deque

R, C = map(int, input().split())
B = [list(input()) for _ in range(R)]
N = int(input())
H = list(map(int, input().split()))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def throw(turn, height) :
    row = R - height
    if turn % 2 == 0 :
        for col in range(C) :
            if B[row][col] == "x" :
                B[row][col] = "."
                break
    else :
        for col in range(C - 1, -1, -1) :
            if B[row][col] == "x" :
                B[row][col] = "."
                break

def bfs(r, c, vistied) :
    queue = deque()
    queue.append((r, c))
    vistied[r][c] = True
    cluster = [(r, c)]

    while queue :
        r, c = queue.popleft()
        for d in range(4) :
            nr, nc = r + dr[d], c + dc[d]
            if 0 <= nr < R and 0 <= nc < C and not vistied[nr][nc] and B[nr][nc] == 'x':
                vistied[nr][nc] = True
                queue.append((nr, nc))
                cluster.append((nr, nc))
    return cluster

def drop(cluster) :
    cluster_set = set(cluster)
    cluster.sort(reverse = True)

    for r, c in cluster :
        B[r][c] = '.'
    
    min_fall = R
    for r, c in cluster :
        fall = 0
        nr = r + 1
        while nr < R and B[nr][c] == '.' and (nr, c) not in cluster_set :
            fall += 1
            nr += 1
        min_fall = min(min_fall, fall)
    
    for r, c in cluster :
        B[r + min_fall][c] = 'x'

for i in range(N) :
    throw(i, H[i])

    visited = [[False] * C for _ in range(R)]
    for r in range(R - 1, -1, -1) :
        for c in range(C) :
            if B[r][c] == 'x' and not visited[r][c] :
                cluster = bfs(r, c, visited)
                is_groud = False
                for r, c in cluster :
                    if r == R - 1 :
                        is_groud = True
                if not is_groud :
                    drop(cluster)
                    break
            else :
                continue

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

이렇게 짰는데 틀렸다, 맞은 코드는 아래와 같다.

항목 원본 코드 정답 코드 문제 원인

1. drop 대상 클러스터 수	공중에 뜬 모든 클러스터를 찾아서 전부 drop 하려고 함	딱 하나의 클러스터만 drop	문제 조건 위반: “떨어질 수 있는 클러스터 하나만 이동”
2. drop 후 visited 갱신	drop 후에도 visited 안 초기화 → 이후 클러스터 판단에 오류 발생	drop 후 visited 다시 초기화하고 바닥과 연결된 것만 다시 마킹	visited가 stale해서 떠 있는 걸로 판단 안 됨
3. 떨어질 수 있는 거리 계산(drop)	cluster_set을 기준으로 min_fall 계산하되 로직 불완전	실제 중력 충돌을 완전히 시뮬레이션하여 fall 계산	일부 블럭이 떨어질 수 없어도 전체가 같이 떨어짐

from collections import deque

R, C = map(int, input().split())
B = [list(input()) for _ in range(R)]
N = int(input())
H = list(map(int, input().split()))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def throw(turn, height):
    row = R - height
    if turn % 2 == 0:
        for col in range(C):
            if B[row][col] == 'x':
                B[row][col] = '.'
                return
    else:
        for col in range(C - 1, -1, -1):
            if B[row][col] == 'x':
                B[row][col] = '.'
                return

def bfs(r, c, visited):
    queue = deque()
    queue.append((r, c))
    visited[r][c] = True
    cluster = [(r, c)]
    while queue:
        r, c = queue.popleft()
        for d in range(4):
            nr, nc = r + dr[d], c + dc[d]
            if 0 <= nr < R and 0 <= nc < C and not visited[nr][nc] and B[nr][nc] == 'x':
                visited[nr][nc] = True
                queue.append((nr, nc))
                cluster.append((nr, nc))
    return cluster

def drop(cluster):
    cluster.sort(reverse=True)
    for r, c in cluster:
        B[r][c] = '.'

    fall = 0
    while True:
        for r, c in cluster:
            nr = r + fall + 1
            if nr >= R or (B[nr][c] == 'x' and (nr, c) not in cluster):
                return fall
        fall += 1

def apply_drop(cluster, fall):
    for r, c in cluster:
        B[r + fall][c] = 'x'

for i in range(N):
    throw(i, H[i])
    
    visited = [[False] * C for _ in range(R)]
    for c in range(C):
        if B[R - 1][c] == 'x' and not visited[R - 1][c]:
            bfs(R - 1, c, visited)

    found = False
    for r in range(R - 1, -1, -1):
        for c in range(C):
            if B[r][c] == 'x' and not visited[r][c]:
                cluster = bfs(r, c, visited)
                f = drop(cluster)
                apply_drop(cluster, f)
                found = True
                break
        if found:
            break

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

지피티가 도와줬다… 틀린 부분은 다음과 같다.

for r in range(R - 1, -1, -1):
    for c in range(C):
        if B[r][c] == 'x' and not visited[r][c]:
            cluster = bfs(r, c, visited)
            drop(cluster)
            break  # ❌ 문제: break는 하나만 drop하게 보이지만 실제 loop가 두 겹이라 여러 번 가능

• visited를 한번 초기화한 뒤 여러 클러스터를 탐색함
• 실제로는 여러 개의 공중 클러스터를 떨어뜨릴 수 있음 (반복 돌면서)
• → 문제에서 금지된 행동

found = False
for r in range(R - 1, -1, -1):
    for c in range(C):
        if B[r][c] == 'x' and not visited[r][c]:
            cluster = bfs(r, c, visited)
            fall = drop(cluster)
            apply_drop(cluster, fall)
            found = True
            break
    if found:
        break

이렇게 수정한다.

• 조건을 만족하는 단 하나의 클러스터만 drop
• 찾으면 즉시 break해서 멈춤

원본

• drop 후에도 visited를 초기화하지 않음
• drop된 클러스터 위치에서 다시 미네랄이 쌓이면,
  • 여전히 visited == False인 곳인데도 다시 drop할 가능성 있음

정답

• drop 직후 visited를 다시 초기화하고, 바닥과 연결된 것만 bfs 처리
• 다음 루프에서 진짜 공중에 떠 있는 미네랄만 판단 가능

for r, c in cluster:
    nr = r + 1
    while nr < R and B[nr][c] == '.' and (nr, c) not in cluster_set:
        fall += 1
        nr += 1

• 한 칸씩 아래로 내려가면서 fall 계산하는데, 중간에 cluster_set 체크가 애매하게 적용되어 일부 놓칠 수 있음

def drop(cluster):
    ...
    fall = 0
    while True:
        for r, c in cluster:
            nr = r + fall + 1
            if nr >= R or (B[nr][c] == 'x' and (nr, c) not in cluster):
                return fall
        fall += 1

• 전체 클러스터가 안전하게 떨어질 수 있을 때까지 전체 시뮬레이션
• 떨어지는 거리(fall)를 한 번에 정확히 계산

이건 너무 어려운문제..