[백준] 미네랄, Python3

문제는 여기!

안녕하세요! 이번 시간에는 백준의 미네랄 문제에 대해 풀이해보겠습니다. 항상 시뮬레이션 문제는 많은 경우의 수를 생각해야하기 때문에 푸는 도중에는 머리가 터질 것 같지만 정답 판정을 받았을 때의 기분은 상당히 짜릿합니다.시간 복잡도따위 일단 맞고보자 그럼 바로 풀이 가보시죠!

나의 풀이 전략

일단 골따리 시뮬레이션 문제들은 참으로 까다롭습니다. 제가 풀이했던 문제들이 많지는 않지만, 시뮬레이션 문제들은 가만 보면 시간 복잡도를 고려하기 보다는 문제를 어떻게 푸느냐가 제일 중요한 것 같아요. 문제에서 보면 동굴의 크기, 막대를 던진 횟수 들이 그리 크지 않습니다.

문제의 핵심은 막대기를 던진 이후 미네랄의 군집화 처리, 미네랄 클러스터들 마다 중력에 의해 바닥으로 떨어지는 것을 처리 이 두 가지인 것 같습니다. 저는 '미네랄 클러스터' 라는 말 자체를 이해 못했습니다. 혹여나 이 게시글을 보러오신 분들이 클러스터의 의미를 알고 싶어서 찾아오신 분도 계실까봐 설명드리자면

이 경우에 문제에서 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 라는 문장이 이해가 잘 안갔는데 쉽게 말해서 상하좌우로 서로 연결된 미네랄 끼리는 같은 군집입니다. 그럼 저 그림에서 군집화를 하면

이렇게 되는 것이죠. 또한, 중력에 의해 미네랄 클러스터를 내려줘야 하기 때문에 저 1 표시가된 미네랄들은

이렇게 됩니다! 이제 코드로 표현할 시간입니다. 먼저 제 코드를 보고 하나씩 설명드릴게요!

import sys
from collections import deque
sys.setrecursionlimit(10**6)
read = lambda: sys.stdin.readline().strip()


def throw(height, order):
    # 왼쪽에서 오른쪽
    if order % 2 == 0:
        j = 0
        while j < c and maps[r - height][j] == '.':
            j += 1
        if 0 <= j < c:
            maps[r - height][j] = '.'

    # 오른쪽에서 왼쪽
    else:
        j = c - 1
        while j >= 0 and maps[r - height][j] == '.':
            j -= 1
        if 0 <= j < c:
            maps[r - height][j] = '.'


def bfs(visit, y, x, count, clusters):
    drc = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque()
    q.append((y, x))
    visit[y][x] = True
    while q:
        now_y, now_x = q.popleft()

        # 군집 표시
        maps[now_y][now_x] = count

        # 해당 군집의 위치 넣어주기
        if count not in clusters:
            clusters[count] = []
        clusters[count].append([now_y, now_x])

        # 탐색하기
        for i in range(4):
            next_y, next_x = now_y + drc[i][0], now_x + drc[i][1]
            if 0 <= next_y < r and 0 <= next_x < c and not visit[next_y][next_x] and maps[next_y][next_x] != '.':
                visit[next_y][next_x] = True
                bfs(visit, next_y, next_x, count, clusters)


# 클러스터들을 내릴 수 있는지 체크하는 함수
def check_down_cluster(number, location):
    for y, x in location:
        if y + 1 >= r or (maps[y + 1][x] != '.' and maps[y + 1][x] != number):
            return False
    return True


def down_cluster(number):
    # 위치들을 .으로 고친 다음, y값을 + 1 해주기
    for i in range(len(clusters[number])):
        maps[clusters[number][i][0]][clusters[number][i][1]] = '.'
        clusters[number][i][0] += 1
    # y + 1 해준 값들을 맵에 군집표시 해주기
    for i in range(len(clusters[number])):
        maps[clusters[number][i][0]][clusters[number][i][1]] = number


if __name__ == "__main__":
    r, c = map(int, read().split())
    maps = []
    for i in range(r):
        maps.append(list(read()))
        for j in range(c):
            if maps[i][j] == 'x':
                maps[i][j] = 0

    n = int(read())
    height = list(map(int, read().split()))
    for i in range(n):
        # 막대 던지기
        throw(height[i], i)

        # 클러스터 체크
        clusters = {}
        visit = [[False for _ in range(c)] for _ in range(r)]
        count = 0
        for y in range(r):
            for x in range(c):
                if not visit[y][x] and maps[y][x] != '.':
                    bfs(visit, y, x, count, clusters)
                    count += 1

        # 클러스터 내려주기
        for key in clusters:
            for j in range(r):
                if check_down_cluster(key, clusters[key]):
                    down_cluster(key)
                else:
                    break

    for i in range(r):
        for j in range(c):
            print('x' if maps[i][j] != '.' else maps[i][j], end='')
        print()

throw

막대를 던지는 함수입니다. 입력받은 막대를 던질 높이 그리고 인덱스를 받아 인덱스가 0으로 나눠지면 왼쪽에서 오른쪽으로 던지고, 그게 아닐 경우는 오른쪽에서 왼쪽으로 던지는 함수입니다. 아참! 저는 맨 처음 maps를 입력받을 때, 모든 미네랄들을 숫자 0으로 표기했습니다. 클러스터 처리를 쉽게 하기 위해서요!

bfs (클러스터 파악하기)

막대를 던졌으니, bfs로 군집화를 해줍니다. clusters를 딕셔너리로 선언하여 해당 클러스터 번호를 key, 클러스터들의 좌표들을 value로 저장해놓았습니다. bfs를 한번 다 돌면 다른 군집을 찾기 위해 count += 1을 처리했습니다.

check_down_cluster, down_cluster (클러스터 중력 처리하기)

먼저 check_down_cluster는 클러스터 번호마다 저장된 모든 위치들의 y좌표를 +1 했을 때, '.'이나 자기 자신이 속한 군집 번호라면 모든 좌표들의 y를 +1 처리 하는지 판별해주는 메서드 입니다. 적으면서 생각해보니 그냥 얼마나 y + 1할 수 있는지 카운트 한 다음에 미네랄 클러스터를 내려주는 것도 괜찮은 방법이겠네요. 이건 녀려분 숙쩨에

down_cluster는 true가 되었을 경우 y좌표를 + 1처리해주는 메서드입니다. 저는 처음에 y좌표들을 수정하고 maps에 수정된 값을 바로 반영하려다가 꼬여서 따로 처리해줬는데요. 한번은 모든 좌표들에 해당하는 maps의 값들을 '.'으로 먼저 바꿔주고, y + 1을 처리했습니다.

그 다음은 y + 1 처리한 좌표들을 maps에 클러스터 번호를 값으로 넣어줍니다.

정답은 maps가 '.'이 아닌 경우는 'x'로, 그렇지 않은 경우는 '.'으로 프린트해주었습니다. 저의 풀이는 여기까지구요! 피드백은 언제나 환영합니다!