[Python 3] BOJ - 2933 "미네랄"

 # 문제 링크

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

2933번: 미네랄

 

# 풀이

 개인적으로 이 문제에서의 핵심은 문제에서 제시한 공중에 떠있는 클러스터의 처리라고 생각한다. 물론 BFS가 필요하나, 단순한 BFS이기 때문에 그것보다는 공중에 떠있는 클러스터가 내려오는 경우에 해당하는 다양한 조건이 좀 더 복잡했다. 단순하게 접근하면 어떤 클러스터의 가장 밑부분의 미네랄이 최초로 닿는 지점까지 움직이는 것이다

<그림 1. 5 X 4의 반례>

 위 그림 1에서 반례를 볼 수 있다. 이 경우에는 굳이 빨간색 클러스터의 맨 밑 미네랄이 바닥에 닿기도 전에 파란색 클러스터에 의해 이동이 중지된다. 따라서 해결할 수 있는 방법은 관점을 공중에 떠있는 클러스터 기준에서 아래로 내려가는 것이 아니라, 각 클러스터에서 자신을 기준으로 위쪽으로 올라가는 것이다. 따라서 공중에 떠있든, 그렇지 않든 모든 클러스터에서 출발하여 다른 클러스터에 속한 미네랄을 만난다면, 거리를 갱신해주는 방식으로 구할 수 있다

<그림 2. 5 X 8의 반례>

 위 그림은 바닥에 붙은 클러스터를 기준으로 내려올 거리를 구하는 방식을 시각화한 것이다. 초록색 클러스터는 빨간색 클러스터 기준으로는 4칸, 파란색 클러스터 기준으로는 3칸이 걸리기 때문에 결과적으로 파란색 클러스터를 만날 것이다

 그런데, 노란색 클러스터는 이러한 방식으로는 거리를 구할 수 없다. 따라서, 모든 경우를 고려하려면 바닥에서의 거리도 고려해야 모든 경우를 구할 수 있다. 그런데 이미 바닥에 붙은 클러스터는 굳이 바닥에서의 거리를 고려할 필요가 없으므로 이 부분을 코드 상에서 예외처리해야 한다

 따라서 코드 상 함수를 창을 던지는 부분, 클러스터를 구하는 부분, 공중에 뜬 클러스터를 내리는 부분으로 크게 3가지로 나눌 수 있고 이를 적절히 구현하면 정답을 구할 수 있다

 

 # 코드

import sys, collections

# get_cluster : 클러스터 번호를 key, 클러스터에 속하는 미네랄의 좌표들의 리스트를 value로 하는 dict를 리턴하는 함수
def get_cluster():
    q = collections.deque()
    res = dict()
    
    # cnt : 각 클러스터 번호
    cnt = 1
    for i in range(n):
        for j in range(m):
            if check[i][j] == -1:
                if arr[i][j] == 'x':
                
                    # 아직 방문하지 않은 미네랄을 기준으로 bfs를 통해 클러스터 계산
                    q.append((i, j))
                    check[i][j] = cnt
                    while q:
                        x, y = q.popleft()
                        for k in range(4):
                            nx, ny = x + dx[k], y + dy[k]
                            if 0 <= nx < n and 0 <= ny < m:
                                if check[nx][ny] == -1:
                                    if arr[nx][ny] == 'x':
                                        q.append((nx, ny))
                                        check[nx][ny] = check[x][y]
                                        
                    # 클러스터 번호 증가
                    cnt += 1
                    
    for i in range(n):
        for j in range(m):
            if check[i][j] != -1:
                # 클러스터 번호가 dict의 key에 있는지에 따라 처리
                if check[i][j] in res:
                    res[check[i][j]].append((i,j))
                else:
                    res[check[i][j]] = [(i, j)]
    return res

# go : get_cluster 함수의 리턴된 dict를 파라미터로 하고 공중에 뜬 클러스터를 아래로 내리는 함수
def go(d):
    # dist : 공중에 뜬 클러스터가 내려가야 할 거리를 저장하는 리스트
             이 때, inf값이라면 바닥에 붙은 클러스터
    dist = [9876543210] * (max(d.keys()) + 1)
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 'x':
            
                # 현재 미네랄에서 위로 진행하면서 다른 클러스터에 붙은 미네랄 탐색
                x, y = i - 1, j
                cnt = 1
                meet = False
                while 0 <= x < n:
                    if arr[x][y] == 'x':
                        meet = True
                        break
                    else:
                        x -= 1
                        cnt += 1
                        
                # 다른 클러스터의 미네랄을 만났을 경우, 거리 갱신
                if meet:
                    if check[x][y] != check[i][j]:
                        dist[check[x][y]] = min(dist[check[x][y]], cnt)

    for i in d:
        # 각 클러스터에 속한 좌표 리스트를 x좌표 기준 역순 정렬
        # 해당 클러스터가 바닥에 있는지 아닌지 판단하기 쉽게하기 위함
        d[i].sort(reverse = True)
        
        # 현재 클러스터의 가장 밑에 있는 미네랄의 x좌표가 바닥이라면 continue
        if d[i][0][0] == n - 1:
            continue
        for j in d[i]:
            x, y = j
            
            # 그림 2에서 본 예외처리 후 이동
            dist[check[x][y]] = min(dist[check[x][y]], n - x)
            if dist[check[x][y]] != 9876543210:
                arr[x][y] = '.'
                # Q : 왜 -1을 더해주는가?
                # A : -1을 더해주지 않으면 만나야 할 미네랄을 덮어씌우기 때문이다
                arr[x + dist[check[x][y]] - 1][y] = 'x'

# throw : 현재 x좌표에서 s의 홀짝성 따라 창을 던지는 함수
          s가 홀수면 왼쪽에서 오른쪽, 짝수면 반대로 진행
def throw(x, s):
    if s % 2 == 0:
        for i in range(m):
            if arr[x][i] == 'x':
                arr[x][i] = '.'
                break
    else:
        for i in range(m - 1, -1, -1):
            if arr[x][i] == 'x':
                arr[x][i] = '.'
                break

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
size = int(sys.stdin.readline())
info = list(map(int, sys.stdin.readline().split()))

# 전체 창을 던진 횟수에 따라 진행
for i in range(size):
    check = [[-1] * m for _ in range(n)]
    throw(n - info[i], i)
    temp = get_cluster()
    go(temp)
    
# 정답 출력
for i in arr:
    print(''.join(i))