[백준/2933/파이썬] 미네랄

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

2933번: 미네랄

Problem

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

조건

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

입출력 조건

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

SOL

 

문제 이해부터 힘들었다.클러스터? 음? 이게 무슨말이야를 생각해서, 우선 질문게시판을 좀 뒤적였고, 다행히 질문게시판에서 이 문제가 돌아가는 메커니즘을 깨닫게 되었다.

 

문제이해

왼쪽 , 오른쪽에서 서로에게 죽창 막대를 던지고 있는데, 이 죽창은 강력해서, 미네랄을 부술 수 있다.

이때, 미네랄 클러스터라는 개념은, 미네랄이 한뭉텅이 인지 아닌지 확인하는 과정이다.(연결요소)

즉, 지금 아래의 그림의 상태는 미네랄 클러스터가 1개인 상태다 .

영 좋지 않은곳에 죽창을 맞아서, 미네랄이 부서지게 되면, 공중에 뜨는 미네랄이 생길 수도 있다. 

아래와 같은 경우다. 2개의 미네랄 클러스터가 생기게 된다. 현실 세계에서는 중력이 존재하기 때문에, 이 미네랄 클러스터는 공중에 뜰수가 없어서, 당연히 밑의 바닥이나, 다른 미네랄클러스터 위에 얹어지게 된다. (빨간색 별으로 위치가 바뀐다)

우리는 이와 같은 과정을 코드로 구현하는 과정을 거치는거다!

입출력 부분

컴퓨터의 배열의 idx의 시작은 0부터인데, 여기서는 한번 더 꼬아서 맨 밑에서부터 1번으로 시작한다.

하지만, 우리는 입출력에서 이걸 평소대로 생각하기 편하게끔, 바꿔줄거다.

target=list(map(lambda x:N-int(x),input().split()))

이렇게 되면, 1 -> N-1, 2 -> N-2, ...N -> 0으로, 우리가 평소에 쓰던 배열의 idx로 입력이 바뀌게 된다. 

 

막대(죽창)을 던지는 부분

 

왼쪽 친구부터 먼저 던지게 만들라고 했으니까, 반

• 복문에서, 던지는 횟수를 이용해서 , 나머지가 0이면 첫번째 던졌던 사람이 던지고, 나머지가 1이면, 두번째 던졌던 사람이 던지는 걸로 해준다.
• 그리고, 죽창을 맞은 미네랄 클러스터는 훼손되게 만들어주고, break_mineral으로 따로 함수를 빼서 구현한다.

 

미네랄이 부서진 부분 

1. 공중에 뜨는 클러스터가 생기는 경우
   • 공중에 뜨는 클러스터가 생기는 경우는, 부서진 곳 주위에 있는 미네랄을 탐색했을 때, 서로 같은 클러스터에 있지 않으면, 이건 미네랄이 부서져서 공중에 클러스터가 생겨버린 경우이다.
   • 공중에 떠있는 클러스터 처리

   • for k in range(4):
             ny=y+dy[k]
             nx=x+dx[k]
             if not (0<=ny<N and 0<=nx<M):
                 continue
             # 미네랄인데, 지금 한뭉치로 안이어져 있고, 공중에 떠있다면 , 2로 표시
             if maps[ny][nx]=="x" and not check[ny][nx]:
                 dq=deque([(ny,nx)])
                 check[ny][nx]=2
                 minerals.append((ny,nx))
                 maps[ny][nx]="."
                 #떨어뜨릴미네랄 뭉치를 탐색.
                 while dq:
                     r,c=dq.popleft()
                     if maps[r+1][c]==".":#바로 밑이 빈공간인 미네랄들은, 따로 계산
                         fallLst.append((r,c))
                     for k in range(4):
                         nr=r+dy[k]
                         nc=c+dx[k]
                         if not(0<=nr<N and 0<=nc<M):
                             continue
                         if maps[nr][nc] =="x" and not check[nr][nc]:
                             check[nr][nc]=2
                             dq.append((nr,nc))
                             minerals.append((nr,nc))
                             maps[nr][nc] ="."

   • 공중에 떠있는 클러스터가 발견되면, 그 클러스터 덩어리들을 다 탐색해야하기 때문에, 여기서도 BFS를 돌아야한다. 바닥에 연결되어있지 않은 클러스터면, "2"로 표시해주고, mineral(원래있던 위치)와 떨어지는 친구들(바닥 밑이 "."인 미네랄들) 떨어질 거리를 계산해주기 위해서, fallLst에 담아준다. fallLst에 담았으면, maps에서는 "."로 바꿔준다.(그래야, 위에 있는 다른 공중에 떠있는 것도 처리가 가능해진다)
   • 이때, 떨어져야 하는 거리를 계산해주기 위해서, 바로 밑이 빈공간인 친구들은 따로 담아준다.
2. 아무일도 없는경우
   • • 공중에 뜨는 클러스터가 생기는 경우는, 부서진 곳 주위에 있는 미네랄을 탐색했을 때, 서로 같은 클러스터에 있으면, 뭐 딱히 문제가 없는 경우이다.

그러므로, 우리는 일단, 미네랄 클러스터를 탐색해줘야하고, 부서진 곳 주위의 미네랄으로 미네랄클러스터를 탐색했을 때, 방문하지 못한곳이 있다면 (연결되어있지 않다면), 이 미네랄 클러스터는 공중에 떠있는거 이므로, 이제 따로 처리를 해줘야한다.

 

미네랄 클러스터 탐색

문제에서, "공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다."라고 나와있기 때문에, 바닥에서 만난 "X"로 BFS를 통해서 연결요소를 찾으면 된다. 그래서 우리가 공중에 떠있지 않은 클러스터들과, 공중에 떠있는 클러스터를 구분해줄거다. 

( 공중에 떠있는 클러스터들은, 바닥에 연결되어 있지 않은 클러스터라고 생각하면 쉽다)

 

떨어질 거리 계산

 

바닥에 닿거나, 다른 클러스터 위에 안착한다면, 그 거리 만큼을 반환해준다.

 

원래있던 위치에서, 떨어진 거리만큼 "x"를 반영해준다.

 

#미네랄
import sys
input = sys.stdin.readline
from collections import deque

N,M = map(int,input().split())
maps=[list(input().rstrip()) for _ in range(N)]
target_cnt=int(input().rstrip())
# 입력 :맨 밑 바닥이 1번 , 맨 위가 R번 
# 거꾸로 되어 있으므로, 길이 - 번호 = 원래 idx
target=list(map(lambda x:N-int(x),input().split()))
#print(target)
dx=[0,1,0,-1]
dy=[1,0,-1,0]
def checkfallDist(fallLst,check):
    fallDist,flag=1,0
    while True:
        for y,x in fallLst:
            #바닥에 닿는 경우
            if y+fallDist ==N-1:
                flag=1
                break
            # 다른 미네랄 위에 떨어지는 경우
            if maps[y+fallDist+1][x] =="x" and check[y+fallDist+1][x]:
                flag=1
                break
        if flag:
            break
        fallDist+=1
    return fallDist

def checkCave():
    check=[[0]*M for _ in range(N)]
    for j in range(M):
        if maps[N-1][j] =="x" and not check[N-1][j]:
            check[N-1][j]=1
            dq=deque([(N-1,j)])
            while dq:
                y,x=dq.popleft()
                for k in range(4):
                    ny=y+dy[k]
                    nx=x+dx[k]
                    if not (0<=ny<N and 0<=nx<M):
                        continue
                    if maps[ny][nx] =="x" and not check[ny][nx] :
                        check[ny][nx] =1
                        dq.append((ny,nx))
    return check

def breakMinerals(y,x):
    #미네랄 클러스터의 모양 체크 
    check=checkCave()
    #공중에 떠있는 미네랄 클러스터 있는지 체크 해줘야함.
    minerals=[]
    fallLst=[]
    for k in range(4):
        ny=y+dy[k]
        nx=x+dx[k]
        if not (0<=ny<N and 0<=nx<M):
            continue
        # 미네랄인데, 지금 한뭉치로 안이어져 있고, 공중에 떠있다면 , 2로 표시
        if maps[ny][nx]=="x" and not check[ny][nx]:
            dq=deque([(ny,nx)])
            check[ny][nx]=2
            minerals.append((ny,nx))
            maps[ny][nx]="."
            #떨어뜨릴미네랄 뭉치를 탐색.
            while dq:
                r,c=dq.popleft()
                if maps[r+1][c]==".":#바로 밑이 빈공간인 미네랄들은, 따로 계산
                    fallLst.append((r,c))
                for k in range(4):
                    nr=r+dy[k]
                    nc=c+dx[k]
                    if not(0<=nr<N and 0<=nc<M):
                        continue
                    if maps[nr][nc] =="x" and not check[nr][nc]:
                        check[nr][nc]=2
                        dq.append((nr,nc))
                        minerals.append((nr,nc))
                        maps[nr][nc] ="."
    if fallLst:
        falldist=checkfallDist(fallLst,check)
        for ny,nx in minerals:
            maps[ny+falldist][nx]="x"

for turn in range(len(target)):
    h=target[turn]#던지는 높이
    #print("h:{}".format(h))
    #왼쪽으로 부터 슛
    if turn %2==0:
        for j in range(M):
            if maps[h][j]=="x":
                maps[h][j]="."
                breakMinerals(h,j)
                break
    #오른쪽으로 부터 슛
    elif turn %2==1:
        for j in range(M-1,-1,-1):
            if maps[h][j] =="x":
                maps[h][j]="."
                breakMinerals(h,j)
                break

for row in maps:
    print(''.join(row))