[Baekjoon] 미네랄(python)

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

문제 접근

시뮬레이션 + BFS로 구현하는 문제이다. 전체적으로 문제풀이 과정은 문제에서 제시하는대로 따라서 구현하면 된다.

 

문제의 핵심 로직은 미네랄 클러스터가 막대기를 던질 때 미네랄이 파괴되면서 클러스터가 분리되는지 확인하는 것이다.

 

미네랄 클러스터는 동서남북으로 인접한 경우만 클러스터로 인정되므로 가장 밑줄의 미네랄들을 BFS나 DFS로 인접한 4방향을 탐색하고 탐색이 종료된 후에 아직 탐색되지 않은 미네랄이 존재하는 경우는 막대기에 의해 분리된 클러스터로 간주하면 된다.

---

풀이 과정

문제 풀이 과정은 미네랄 파괴 -> 클러스터 체크 -> 분리된 클러스터 낙하를 구현하면 된다.

 

1. 미네랄 파괴

for i, height in enumerate(throwing):
    if i % 2 == 0:
        for i in range(C):
            if cave[R - height][i] == "x":
                cave[R - height][i] = "."
                break
    else:
        for i in range(C - 1, -1, -1):
            if cave[R - height][i] == "x":
                cave[R - height][i] = "."
                break

문제의 조건에 따르면 막대기를 던지는 경우는 왼쪽/오른쪽을 번갈아가면서 던지도록 되어있다.

 

따라서 입력의 순서가 짝수이면 왼쪽에서 던지는 경우 홀수이면 오른쪽에서 던지는 경우로 생각하면 된다.

 

미네랄 파괴는 "x" -> "."로 변경해주면 된다.

 

2. 클러스터 체크

def check_cluster():
    """
    가장 아래부터 클러스터를 체크하면 남은 'x'는 분리된 클러스터이다
    """
    checked = [[False] * C for _ in range(R)]

    q = deque()

    # 가장 아랫줄이 미네랄이면 모두 탐색에 넣도록 한다.
    for i in range(C):
        if cave[R - 1][i] == "x":
            q.append([R - 1, i])

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (
                nx < 0
                or nx >= R
                or ny < 0
                or ny >= C
                or checked[nx][ny]
                or cave[nx][ny] == "."
            ):

                continue

            checked[nx][ny] = True
            q.append([nx, ny])

    return checked

가장 밑줄에 있는 미네랄을 모두 탐색의 시작점으로 잡아 클러스터를 체크하도록 한다.

미네랄은 항상 바닥에 붙어있어야 하고, 바닥에 붙어있지 않은 경우는 클러스터에 포함된 경우이다.

 

따라서 바닥에 있는 미네랄의 좌표를 모두 시작점으로 탐색하면 위의 그림과 같이 빨간 영역과 같은 분리된 클러스터를 체크할 수 있다.

 

3. 분리된 클러스터 낙하

def fall(checked):
    height = R

    for i in range(R - 1, -1, -1):
        for j in range(C):
            if cave[i][j] == "." or checked[i][j]:
                continue

            # 바닥으로 떨어지는 경우
            height = min(height, R - i - 1)

            for k in range(i + 1, R):
                if cave[k][j] == "x" and checked[k][j]:
                    height = min(height, k - i - 1)

    for i in range(R - 1, -1, -1):
        for j in range(C):
            if cave[i][j] == "." or checked[i][j]:
                continue

            cave[i + height][j] = "x"
            cave[i][j] = "."

주어진 조건에 따르면 클러스터는 바닥에 닿을 때까지 떨어지고 클러스터의 모양은 유지하면서 떨어져야 한다.

 

따라서, 우리는 클러스터가 떨어질 수 있는 높이의 최솟값을 구해야 클러스터의 모양을 유지할 수 있다.

 

 

분리된 클러스터들이 낙하하고 나면 결과는 위의 그림과 같을 것이다.

---

정답 코드

"""
    백준 2933번 미네랄
"""
import sys
from collections import deque
from tabnanny import check

R, C = list(map(int, sys.stdin.readline().split()))

cave = []


for _ in range(R):
    cave.append(list(sys.stdin.readline()[:-1]))

N = int(sys.stdin.readline())

throwing = list(map(int, sys.stdin.readline().split()))
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]


def print_cave():
    global cave
    print(*["".join(c) for c in cave], sep="\n")


def check_cluster():
    """
    가장 아래부터 클러스터를 체크하면 남은 'x'는 분리된 클러스터이다
    """
    checked = [[False] * C for _ in range(R)]

    q = deque()

    # 가장 아랫줄이 미네랄이면 모두 탐색에 넣도록 한다.
    for i in range(C):
        if cave[R - 1][i] == "x":
            q.append([R - 1, i])

    while q:
        x, y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (
                nx < 0
                or nx >= R
                or ny < 0
                or ny >= C
                or checked[nx][ny]
                or cave[nx][ny] == "."
            ):

                continue

            checked[nx][ny] = True
            q.append([nx, ny])

    return checked


def fall(checked):
    height = R

    for i in range(R - 1, -1, -1):
        for j in range(C):
            if cave[i][j] == "." or checked[i][j]:
                continue

            # 바닥으로 떨어지는 경우
            height = min(height, R - i - 1)

            for k in range(i + 1, R):
                if cave[k][j] == "x" and checked[k][j]:
                    height = min(height, k - i - 1)

    for i in range(R - 1, -1, -1):
        for j in range(C):
            if cave[i][j] == "." or checked[i][j]:
                continue

            cave[i + height][j] = "x"
            cave[i][j] = "."


for i, height in enumerate(throwing):
    if i % 2 == 0:
        for i in range(C):
            if cave[R - height][i] == "x":
                cave[R - height][i] = "."
                break
    else:
        for i in range(C - 1, -1, -1):
            if cave[R - height][i] == "x":
                cave[R - height][i] = "."
                break

    checked = check_cluster()

    fall(checked)

print_cave()