[백준/3197/파이썬] 백조의 호수

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

3197번: 백조의 호수

Problem

• 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
• 며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

조건

• 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
• 백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
• 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
• 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

SOL

슬픈 백조 두마리를 구해보자.

 

1. 물이 움직인다고 생각하는게 편하다.

2. 이때, 매번 물이 움직이는걸로 하기에는 물이 엄청 커지면 N^2을 매번 해야할 수 있으므로, 최적화 과정이 필요하다.

3. 물이 움직이고 , 다음부터는 녹은 얼음 부분만 다시 물이되고, 이런 과정을 반복하면 된다. 이렇게되면, 가장자리만 계속 퍼지는 형태로 구현이 가능함!

4. 백조가 만날 수 있는지 확인한다. 이때, 백조는 한마리의 백조가 다른 한마리의 백조에 닿으면 되므로, 백조의 위치도 모든 경우보다는 각각의 가장자리에서 퍼져나아가는게 더 효율적이다.

 

from collections import deque
import sys
input = sys.stdin.readline
dx=[0,1,0,-1]
dy=[1,0,-1,0]

N,M =map(int,input().split())

lakes=[list(input().rstrip()) for _ in range(N)]

wv=[[False]*M for _ in range(N)]
sv=[[False]*M for _ in range(N)]

dqWater,tmp_water=deque(),deque()
dqSwan,tmp_swan=deque(),deque()
ey,ex,ans=0,0,0

def water():
    while dqWater:
        y,x = dqWater.popleft()
        lakes[y][x]="."
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if ny<0 or ny>=N or nx<0 or nx>=M or wv[ny][nx]:
                continue
            if lakes[ny][nx] ==".":
                dqWater.append((ny,nx))
            else:
                tmp_water.append((ny,nx))
            wv[ny][nx] = True

def swan():
    while dqSwan:
        y,x =dqSwan.popleft()
        if y==ey and x==ex:
            return True
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if ny<0 or ny>=N or nx<0 or nx>=M or sv[ny][nx]:
                continue
            if lakes[ny][nx] ==".":
                dqSwan.append((ny,nx))
            else:
                tmp_swan.append((ny,nx))
            sv[ny][nx] = True
    return False

for i in range(N):
    for j in range(M):
        if lakes[i][j] =="L":
            if not dqSwan:
                #첫번째 백조
                dqSwan.append((i,j))
                sv[i][j] = True
            else:
                ey,ex=i,j
            lakes[i][j] ="."
        if lakes[i][j] ==".":
            dqWater.append((i,j))
            wv[i][j] = True

while True:
    water()
    if swan():
        break
    dqWater=tmp_water
    dqSwan=tmp_swan
    tmp_water=deque()
    tmp_swan=deque()
    ans+=1

print(ans)