2933: 미네랄

풀이 시간

• 2h
• 반례 찾는 게 힘들었다

구현 방식

• 이 문제의 포인트는 클러스터 별로 중력을 작용해주는 부분이었던 것 같다.
  -> 이렇게 해주기 위해선 클러스터에 대한 정보를 dictionary에 담아서 처리해주는 게 편하다 (key는 cluster number, value는 [(x1, y1), (x2, y2) ... ])

• throw()
  -> 미네랄을 파괴해주는 부분을 구현한 함수/ 이부분은 쉽게 구현할 수 있음

• find_cluster()
  -> clusters 딕셔너리를 완성하여 반환해주는 함수
  -> 2중 for문을 순회하면서 global 2차원 리스트인 visit에 cluster number를 모두 표시해주고, 다시 2중 for문을 순회하면서 visit을 기반으로 clusters 딕셔너리를 완성시켜준다

• gravity()
  • 1) distance 딕셔너리를 이용하여 각 cluster 별로 내려와야할 거리를 구해주었다
    • distance를 int(10e9)로 초기화한 후, 모든 'x'부분에서 위로 올라가면서 cluster 별로 distance의 최솟값을 갱신해주었다
      -> 이 때도 global visit 리스트를 이용하여, 위로 올라가면서 닿는 cluster가 자기 자신이 아닌 경우(visit[x][y] != visit[r][c])에만 distance를 갱신해줘야한다
  • 2) distance를 완성한 후에, clusters를 순회하면서 distance만큼 각 cluster를 내려줘야 한다.
    • 여기에서도 고려해줘야할 예외 사항이 있는데, 1. 바닥에 붙어 있는 cluster인 경우에는 내려줄 필요가 없으니 바로 continue 해줘야한다. 2. 바닥으로 떨어지는 cluster인 경우 distance값이 아직 int(10e9)인 상태일 수 있기 때문에, 한 번 더 distance[key] = min(distance[key], R-x)를 수행해주어야 한다.

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def throw(direction, height):
    if direction == 0: #왼쪽에서 오른쪽으로
        y = -1
        for c in range(C):
            y += 1
            if board[height][y] == 'x':
                board[height][y] = '.'
                break
    elif direction == 1: #오른쪽에서 왼쪽으로
        y = C
        for c in range(C):
            y -= 1
            if board[height][y] == 'x':
                board[height][y] = '.'
                break

def find_cluster():
    global visit
    queue = deque([])
    clusters = dict()

    cnum = 1 #cluster number
    for r in range(R):
        for c in range(C):
            if visit[r][c] == -1:
                if board[r][c] == 'x':
                    queue.append((r, c)); visit[r][c] = cnum
                    while queue:
                        x, y = queue.popleft()
                        for i in range(4):
                            nx = x + dx[i]; ny = y + dy[i]
                            if 0 <= nx < R and 0 <= ny < C:
                                if board[nx][ny] == 'x' and visit[nx][ny] == -1:
                                    queue.append((nx, ny)); visit[nx][ny] = cnum
                    cnum += 1

    for r in range(R):
        for c in range(C):
            if visit[r][c] != -1:
                if visit[r][c] in clusters:
                    clusters[visit[r][c]].append((r, c))
                else:
                    clusters[visit[r][c]] = [(r, c)]

    return clusters

def gravity(clusters):
    global visit
    distance = {i: int(10e9) for i in range(1, max(clusters.keys()) + 1)} #각 cluster가 내려와야할 거리

    # distance 완성해주기
    for r in range(R):
        for c in range(C):
            if board[r][c] == 'x':
                
                x = r-1; y = c; cnt = 1; flag = False
                while 0 <= x < R:
                    if board[x][y] == 'x':
                        flag = True; break
                    x -= 1; cnt += 1
                
                if flag and visit[x][y] != visit[r][c]:
                    distance[visit[x][y]] = min(distance[visit[x][y]], cnt)

    # distance만큼 cluster 내려주기
    for key, value in clusters.items(): # key는 cluster number, value는 [(x1, y1), (x2, y2) ... ]
        value.sort(reverse = True)
        if value[0][0] == R-1: continue #바닥에 붙어 있는 cluster

        for x, y in value:
            distance[key] = min(distance[key], R - x) #예외처리: 공중에 떠있는 cluster (바닥으로 떨어지는 경우)
            if distance[key] != int(10e9):
                nx = x + distance[key] - 1; ny = y
                board[x][y] = '.'; board[nx][ny] = 'x'


R, C = map(int, sys.stdin.readline()[:-1].split())
board = []
for r in range(R):
    board.append(list(sys.stdin.readline()[:-1]))
N = int(sys.stdin.readline()[:-1])
sticks = list(map(int, sys.stdin.readline().strip().split()))

for n in range(N):
    throw(n % 2, R - sticks[n])

    visit = [[-1] * C for _ in range(R)] #visit에 cluster number를 기록
    clusters = find_cluster()
    gravity(clusters)

for i in range(R):
    print(''.join(map(str, board[i])))

결과

for n in range(N):
    width = throw(n % 2, R - sticks[n])

    if width:
        visit = [[-1] * C for _ in range(R)] #visit에 cluster number를 기록
        clusters = bfs_cluster()
        gravity(clusters)

• 메인에서 미네랄이 파괴된 경우에만 클러스터를 내려주는 작업을 수행해줬는데, 그냥 모든 경우에 클러스터를 내려주는 작업을 해줬어야 했다.

for n in range(N):
    throw(n % 2, R - sticks[n])

    visit = [[-1] * C for _ in range(R)] #visit에 cluster number를 기록
    clusters = find_cluster()
    gravity(clusters)