[백준 18500번] 파이썬 - 미네랄 2

백준 18500 - 미네랄 2

시간 제한 1초, 메모리 제한 512MB

# 조건

• 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다.
• 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다.
• 싸움은 동굴에서 벌어진다.
• 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다.
• 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다.
  • 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다.
• 창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다.
• 두 사람은 턴을 번갈아가며 막대기를 던진다.
  • 막대를 던지기 전에 던질 높이를 정해야 한다.
  • 막대는 땅과 수평을 이루며 날아간다.
• 막대가 날아가다가 미네랄을 만나면, 그 칸에 있는 미네랄은 모두 파괴되고 막대는 그 자리에서 이동을 멈춘다.
• 미네랄이 파괴된 이후에 남은 클러스터가 분리될 수도 있다.
• 새롭게 생성된 클러스터가 떠 있는 경우에는 중력에 의해서 바닥으로 떨어지게 된다.
  • 떨어지는 동안 클러스터의 모양은 변하지 않는다.
• 클러스터는 다른 클러스터나 땅을 만나기 전까지 게속해서 떨어진다.
• 클러스터는 다른 클러스터 위에 떨어질 수 있고, 그 이후에는 합쳐지게 된다.
• 동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다.
• 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 동굴의 크기 R과 C가 주어진다. (1 ≤ R,C ≤ 100)
• 다음 R개 줄에는 C개의 문자가 주어지며, '.'는 빈 칸, 'x'는 미네랄을 나타낸다.
• 다음 줄에는 막대를 던진 횟수 N이 주어진다. (1 ≤ N ≤ 100)
• 마지막 줄에는 막대를 던진 높이가 주어지며, 공백으로 구분되어져 있다.
• 모든 높이는 1과 R사이이며, 높이 1은 행렬의 가장 바닥, R은 가장 위를 의미한다.
• 첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
• 공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다.

출력

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

# 접근 방법

• 미네랄이 파괴되고 새로운 클러스터가 형성되었을 때, 공중에 떠있다면 떨어진다.

  • 즉, 미네랄의 어떤 부분이 파괴되었을 때 덩어리 별로 조사하고 해당 덩어리를 조사해준다.

• 막대를 던져 미네랄을 파괴하는 함수, 클러스터를 확인하는 함수, 미네랄이 떨어지는 함수를 구현해준다.

• destroy 함수

  • 화살을 쏘는 인덱스에 따라 왼쪽 또는 오른쪽에서부터 탐색하며 미네랄을 만났을 때 파괴하고, 해당 행을 저장해준다.
  • 또한, 아래에서부터 1이므로 R - 주어진 높이를 빼준다.
  • 파괴를 했다면 해당 미네랄 4방향을 살펴보고 부서진 미네랄과 덩어리였던 곳들을 담아준다.
  • 이 리스트를 반환해준 후 미네랄 덩어리를 확인해준다.

• check 함수

  • 분리된 덩어리를 bfs를 통해 탐색해준다.
  • 이 때, 떨어지는 덩어리 중 미네랄 또는 바닥에 닿는 위치를 fall_list 에 기록해준다.
  • 땅을 만났다면 이 덩어리는 추락하지 않으므로 return 해주고 bfs 탐색이 끝까지 온 경우는 떨어지는 경우 이므로 fall 함수를 시작해준다.

• fall 함수

  • check 함수에서 반환 된 visited 리스트와 fall_list를 활용해준다.
  • 1칸씩 떨어지는 변수인 fall_dist를 선언해준다.
  • 이 때, fall_dist를 더한 값은 떨어지는 위치이므로
  • fall_list를 탐색하며 바로 아래가 바닥이거나, 2칸 아래가 미네랄이라면 종료해주고 visited 배열이 True인 곳을 fall_dist만큼 추락시키고 '.' 으로 변경시켜준다.

• 계속 시작하자마자 틀렸다.. 맞왜틀..

• 출력시 칸 사이에 빈칸이 있으면 안되는데 빈칸이 들어가서 오답이였다.. 출력 형식 꼭 확인하자.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def fall(f_list, visited):  
    fall_dist, flag = 1, True  
    while True:  
        for fi, fj in f_list:  
            # 아래가 바닥이거나  
            # 2칸 아래가 미네랄이면 종료            
            if fi+fall_dist == R-1 or (arr[fi+fall_dist+1][fj] == 'x' and not visited[fi+fall_dist+1][fj]):  
                flag = False  
                break  
        if not flag:  
            break  
        fall_dist += 1  

    # 추락시켜주기  
    # 아래에서부터 해주어야 한다.    
    # 바닥 위에서부터 체크    
    for fi in range(R-fall_dist-1, -1, -1):  
        for j in range(C):  
            if arr[fi][j] == 'x' and visited[fi][j]:  
                arr[fi][j] = '.'  
                arr[fi+fall_dist][j] = 'x'  

def check(ci, cj):  
    visited = [[False] * C for _ in range(R)]  
    q = deque()  
    q.append((ci, cj))  
    visited[ci][cj] = True  
    fall_list = []  
    while q:  
        si, sj = q.popleft()  
        # 바닥이라면 추락할 필요 없으니 return  
        if si == R-1:  
            return  
        if arr[si+1][sj] == '.':  
            fall_list.append((si, sj))  
        for d in range(4):  
            ni, nj = si+di[d], sj+dj[d]  
            if 0<=ni<R and 0<=nj<C and visited[ni][nj] == False and arr[ni][nj] == 'x':  
                q.append((ni, nj))  
                visited[ni][nj] = True  

    # 바닥에 닿지 않았다면 추락해야되므로 fall 함수  
    fall(fall_list, visited)  


def destroy(direct, height):  
    des_mineral = -1  
    # 왼쪽에서 던짐  
    if not direct:  
        for j in range(C):  
            if arr[height][j] == 'x':  
                arr[height][j] = '.'  
                des_mineral = j  
                break  
    else:  
        for j in range(C-1, -1, -1):  
            if arr[height][j] == 'x':  
                arr[height][j] = '.'  
                des_mineral = j  
                break  

    # 미네랄 파괴후, 새로운 클러스터가 생기고  
    # 클러스터가 떨어지는 조건에 만족한다면 리스트에 담아 반환해준다.    
    new_cluster = []  
    if not des_mineral == -1:  
        for d in range(4):  
            ni, nj = height + di[d], des_mineral + dj[d]  
            if 0<=ni<R and 0<=nj<C and arr[ni][nj] == 'x':  
                new_cluster.append([ni, nj])  
    return new_cluster  



R, C = map(int, input().split())  
arr = [list(input().rstrip()) for _ in range(R)]  
N = int(input())  
query = [*map(int, input().split())]  
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  

for idx, h in enumerate(query):  
    val = destroy(idx % 2, R-h)  
    if val:  
        for i, j in val:  
            check(i, j)  

for i in arr:  
    print(''.join(i))