[Python] 백준 2933번: 미네랄

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

2933번: 미네랄

 

 

---

문제 설명

 

• 창영(=왼쪽), 상근(=오른쪽)이가 번갈아가며 막대기를 던진다.
• 막대를 던지기 전에 던질 높이를 정한다.
• 막대는 땅과 수평을 이루며 날아간다.
• 막대가 미네랄을 만나면, 미네랄은 없어지고 막대기도 그자리에서 소멸된다.

 

• 클러스터 : 미네랄 집합이라고 생각하면 된다.
• 동 서 남 북 으로, 서로 연결되어 있으면 하나의 클러스터이다.

 

• 미네랄이 부서짐에 따라, 새로운 클러스터가 생성될 수 있다.
• 새롭게 생성된 클러스터가 공중에 있을 경우, 다른 클러스터나 땅을 만나기 전까지 계속해서 떨어뜨려야 한다.
• 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐진다.

 

출력

모든 막대를 던지고 난 이후에 미네랄 모양을 구하면 된다.

 

 

---

문제 풀이 방법

 

막대에 의해 미네랄이 부서지고, 새로운 클러스터가 생겼다고 가정하자.

이 새로운 클러스터는 공중에 있을 수도 있고, 아닐수도 있다.

 

맵의 가장 밑바닥을 하나씩 훑으면서 미네랄을 발견하면, 그 미네랄을 포함하고 있는 클러스터를 체크한다.

 

이 과정을 다 끝마치고 나서, 훑지 못한 미네랄이 있다면, 이는 공중에 떠 있는 미네랄 클러스터이다.

 

이렇게 해도 시간이 많이 걸렸는데, 방법은 비슷하게 하되 계산 과정을 줄일 수 있는 방법을 찾는게 좋을 것 같다.

 

 

---

Code

 

## 바닥과 연결되어 있는 미네랄 클러스터를 제거한다.
def remove_mineral(i, j):
    stack = [(i, j)]
    while stack:
        node = stack.pop()
        board_copy[node[0]][node[1]] = True
        for di, dj in zip(dxs, dys):
            ni, nj = node[0]+di, node[1]+dj
            if ni < 0 or ni >= n or nj < 0 or nj >= m: continue
            if not board_copy[ni][nj]: stack.append((ni, nj))

 

## 공중에 있는 미네랄 클러스터를 반환한다. 없으면 빈 딕셔너리를 반환한다.
def air_mineral():
    air_dict = dict()
    for i in range(n):
        for j in range(m):
            if not board_copy[i][j]:
                if j in air_dict.keys():
                    air_dict[j].append(i)
                else:
                    air_dict[j] = [i]
    return air_dict

 

if __name__ == '__main__':
    ## 입력값
    n, m = map(int, input().split())
    board = [list(input()) for _ in range(n)]
    shoot = int(input())
    shoot_list = list(map(lambda x: n - int(x), input().split()))
    board_copy = [[False]*m for _ in range(n)]
 
    ## 남 동 서 북
    dxs = (0, 1, -1, 0)
    dys = (1, 0, 0, -1)
 
    for order in range(len(shoot_list)):
        x = shoot_list[order]  # 막대 던지는 높이
        T = 0  # 0(=미네랄이 파괴되지 않았다.) 1(=미네랄이 파괴되었다.)
 
        if order % 2 == 0:  # 왼쪽
            for y in range(m):  # 왼쪽에서부터 미네랄 탐색
                if board[x][y] == 'x':  # 미네랄 발견하면
                    board[x][y] = '.'  # 미네랄 파괴
                    T = 1
                    break
 
        elif order % 2 == 1:  # 오른쪽
            for y in range(m - 1, -1, -1):  # 오른쪽에서부터 미네랄 탐색
                if board[x][y] == 'x':  # 미네랄 발견하면
                    board[x][y] = '.'  # 미네랄 파괴
                    T = 1
                    break
 
        ## 미네랄이 파괴된 경우, 공중에 떠있는 클러스터가 생길 가능성이 있으므로
        if T == 1:
            for i in range(n):
                for j in range(m):
                    if board[i][j] == '.': board_copy[i][j] = True
                    else: board_copy[i][j] = False
            
            ## board_copy에서 공중에 있는 클러스터를 제외한 나머지 미네랄들을 전부 제거한다.
            for col in range(m):
                if not board_copy[-1][col]: remove_mineral(n - 1, col)
            
            ## 공중에 떠 있는 미네랄 클러스터가 있는지 확인한다.
            air_cluster = air_mineral()
            
            ## 만약 공중에 떠 있는 미네랄이 있다면 밑으로 떨어뜨린다.
            if air_cluster:
                minv = 100
                ## 떨어져야 하는 높이를 구한다.
                for y in air_cluster.keys():
                    for x in air_cluster[y]:
                        for fx in range(x+1, n):
                            if board[fx][y] == 'x' and fx not in air_cluster[y]:
                                minv = min(minv, fx-x-1)
                        if fx == n-1 and board[fx][y] == '.':
                            minv = min(minv, fx-x)
                ## 떨어뜨린다
                for y in air_cluster.keys():
                    air_cluster[y].sort(reverse=True)
                    for x in air_cluster[y]:
                        board[x][y] = '.'
                        board[x+minv][y] = 'x'
    ## 출력
    for row in board:
        print(''.join(row))