[BOJ 2933 🥇1] 미네랄 (Python)

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

2933번: 미네랄

문제

창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.

동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.

창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다.

막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.

미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다. 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다. 떨어지는 동안 클러스터의 모양은 변하지 않는다. 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다. 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.

다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)

마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다. 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다. 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.

공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 클러스터가 떨어질 때, 그 클러스터 각 열의 맨 아래 부분 중 하나가 바닥 또는 미네랄 위로 떨어지는 입력만 주어진다.

출력

입력 형식과 같은 형식으로 미네랄 모양을 출력한다.

예제 입력 1

5 6
......
..xx..
..x...
..xx..
.xxxx.
1
3

예제 출력 1

......
......
..xx..
..xx..
.xxxx.

예제 입력 2

8 8
........
........
...x.xx.
...xxx..
..xxx...
..x.xxx.
..x...x.
.xxx..x.
5
6 6 4 3 1

예제 출력 2

........
........
........
........
.....x..
..xxxx..
..xxx.x.
..xxxxx.

예제 입력 3

7 6
......
......
xx....
.xx...
..xx..
...xx.
....x.
2
6 4

예제 출력 3

......
......
......
......
..xx..
xx.xx.
.x..x.

 

⭕ CODE

from collections import deque

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def broke(h, left):
    # 높이 h이므로 좌표에서 x좌표는 n-h
    x = n - h
    y = 0
    # 부술게 있는지 없는지 확인하기 위한 flag
    flag = 0

    # 왼쪽에서 날린다면
    if left == 1:
        # 왼쪽부터 x가 나오는지 확인
        for i in range(m):
            # 미네랄이 있다면
            if arr[x][i] == 'x':
                # 부수고 y좌표 업데이트
                # 부수었으니 flag = 1
                arr[x][i] = '.'
                y = i
                flag = 1
                break

    # 오른쪽에서 날린다면 반대로 오른쪽 부터 찾기
    elif left == - 1:
        for i in range(m - 1, -1, -1):
            if arr[x][i] == 'x':
                arr[x][i] = '.'
                y = i
                flag = 1
                break

    # x,y 좌표와 flag 리턴
    return x, y, flag


def bfs(x, y):
    global cluster
    q = deque()
    q.append((x, y))
    visited[x][y] = 1
    cluster.append((x, y))
    while q:
        x, y = q.popleft()

        # 바닥이라면 공중에 떠있는게 아니므로
        if x == n - 1:
            # cluster를 빈 리스트로 리턴
            cluster = []
            return cluster

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

            if 0 <= nx < n and 0 <= ny < m:
                if arr[nx][ny] == 'x' and visited[nx][ny] == 0:
                    q.append((nx, ny))
                    visited[nx][ny] = 1
                    cluster.append((nx, ny))
    return cluster


def drop(cluster):
    # 나중에 떨어트릴 때 아래에서 부터 떨어트려야지 위에꺼랑 중복이 안된다.
    # 그를 해결하기 위한 정렬
    cluster.sort(key=lambda x: (x[1], -x[0]))
    droplist = []

    # 자기 바로 밑이 미네랄이 아니라면 떨어트릴 리스트에 추가
    for x, y in cluster:
        if arr[x + 1][y] != 'x':
            droplist.append((x, y))
    
    # 최대 100칸이므로 101칸으로 설정
    mindrop = 101
    
    for x, y in droplist:
        count = 0

        while True:
            # 한칸 늘려주기
            x += 1
            # 바닥에 도착한다면 종료
            if x >= n:
                break
            # 밑으로 가는 칸이 미네랄이면서
            # 그 밑으로 가는 칸이 cluster에 없었더라면
            # 다른 클러스터에 만난것이므로 종료
            if arr[x][y] == 'x' and (x, y) not in cluster:
                break
            
            # 높이 1 증가
            count += 1
        
        # 떨어트릴 최소 높이 구하기
        mindrop = min(mindrop, count)

    # cluster에 대해서 최소높이만큼 떨어트리고
    # 원래 자리는 빈공간으로 만들기
    for x, y in cluster:
        arr[x][y] = '.'
        arr[x + mindrop][y] = 'x'


n, m = map(int, input().split())

arr = [list(input()) for _ in range(n)]

cnt = int(input())

stick = list(map(int, input().split()))

left = 1

# 던지는 높이 h
for h in stick:
    # 부순 x,y좌표와 부수었는지 확인하기 위한 flag
    x, y, flag = broke(h, left)
    # 다음번에는 반대방향에서 던저야하므로 left에 -1 곱해주기
    left *= -1

    # flag가 0이라면 부수지 못했다.
    # 아래 동작 할 필요가 없다.
    if flag == 0:
        continue

    # cluster를 담기위한 list
    cluster = []

    # 부순 x,y좌표의 주변 4방향에 대해서
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        visited = [[0] * m for _ in range(n)]

        # 격자안에 존재하고 미네랄이고 방문한적이 없다면
        if 0 <= nx < n and 0 <= ny < m:
            if arr[nx][ny] == 'x' and visited[nx][ny] == 0:
                bfs(nx, ny)

                # 공중에 떠있는 cluster가 존재한다면
                if cluster:
                    # 떨어트리자
                    drop(cluster)

for i in range(n):
    for j in range(m):
        print(arr[i][j], end='')
    # 마지막칸은 공백이 아니다.
    if i != n - 1:
        print()

✏️ Comment

한달전에 풀다가 실패한 문제이다. 나중에 공중에 있는 클러스터를 확인하고 떨어트릴 때 아래칸부터 떨어져야지 오류가 생기지 않는다. 위에서 부터 떨어지면 원래 존재하던 자리에 떨어져서 나중에 아래에 삭제 당할 경우가 생기기 때문에 이를 방지하기 위해 cluster를 sort해준다.

마지막줄은 공백으로 출력하면 안된다. 이런 조건 하나하나 까먹지 말자

처음에는 떨어지는 높이를 바닥면에서만 확인을 해주어서 이 부분도 반례가 존재한다.

9 8
........
.xxxx...
.x......
.x.xxxx.
.x....x.
.x....x.
.xxxx.x.
....xxx.
......x.
1
2

output:
........
........
.xxxx...
.x.xxxx.
.x....x.
.x....x.
.x....x.
.xxxxxx.
......x.​

 

위 예시처럼 위에는 떨어지는 높이가 1칸이고 아래는 2칸인 경우가 있다.