백준 3197 : 백조의 호수 (Python)

본문 링크

from collections import deque
import sys
input=sys.stdin.readline

def Swans():
    global Find,deq3
    deq4 = deque()

    while deq3:
        x,y=deq3.popleft()
        for i in range(4):
            nx = x + dx[i] ; ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if graph[nx][ny] == "." and not visit_Swans[nx][ny]:
                    visit_Swans[nx][ny] = True
                    deq3.append([nx, ny])
                elif graph[nx][ny]=="X" and not visit_Swans[nx][ny]:
                    visit_Swans[nx][ny]=True
                    deq4.append([nx,ny])
                elif graph[nx][ny]=="L" and not visit_Swans[nx][ny]:
                    Find=True
                    break
    deq3=deq4

def BFS():
    global deq
    Length=len(deq)
    for _ in range(Length):
        x,y=deq.popleft()
        for i in range(4):
            nx=x+dx[i] ; ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if graph[nx][ny]=="X" and not visit[nx][ny]:
                    graph[nx][ny]='.'
                    visit[nx][ny]=True
                    deq.append([nx,ny])




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

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

graph=[ list(input().rstrip()) for _ in range(N) ]
deq=deque()

labudovi=[]
visit=[ [False]*M for _ in range(N) ]
visit_Swans=[ [False]*M for _ in range(N) ]
for i in range(N):
    for j in range(M):
        if graph[i][j]!="X":
            deq.append([i,j])
        if graph[i][j]=="L":
            labudovi.append([i,j])

deq3=deque()
deq3.append([labudovi[0][0] , labudovi[0][1]])

visit_Swans[labudovi[0][0]][labudovi[0][1]]=True

Find=False
Day=0
while Find==False:
    Swans()
    if Find==False:
        BFS()
        Day+=1

print(Day)

📌 어떻게 접근할 것인가?

BFS 문제지만 여러가지 생각해야할 점이 많습니다.

매번 모든 물에 대해서 얼음의 녹는것을 탐색한후
다시 백조가 서로 만날수있는지 탐색을 하면 시간초과가 납니다.

따라서 덱을 2개를 사용해야합니다.
그래프 값이 물이라서 주변에 얼음을 녹일 수 있다면
덱을 하나 추가로 만들어서 얼음이 녹은 지점의 좌표를 넣어줍니다.

이후 모두 얼음을 녹였다면 얼음이 녹은 좌표를 원래의 덱에 넣는다면
시간을 조금더 단축할수 있습니다.

질문게시판에 어떤분이 깔끔하게 정리해주셨습니다.

📌 2개의 그래프 탐색

하지만 문제에서는 두 백조가 만나는 최소 일수를 구하는 것입니다.
얼음을 녹이는 방법을 최적화 했지만 백조가 만나는것을 어떻게 확인할 수 있을까요?

간단하게

• 얼음을 녹인다 - 녹인지점만큼 백조의 좌표에서 그래프 탐색을 한다

이 두 과정을 계속반복해서 하나의 백조의 좌표에서 다른 백조의 좌표에 도달할수 있을때 까지 반복합니다.

따라서 총 2개의 그래프 탐색 함수를 만들었습니다.

1. 백조를찾는 $Swans$ 함수.

$deq3$ 에서는 백조를 기점으로 다른 백조를 찾는 $BFS$ 를 합니다.
이때 $graph$ 가 물일때는 $deq3$ 에 원소를 추가하여 계속 탐색합니다.

만약 얼음일때는 $deq4$ 에 원소를 추가한다.

백조를 만났을때는 $Find$ 라는 변수값을 $True$ 로 변해준후 $break$ 해줍니다.
또한 매번 모든방문에 대해 처리를 해줍니다.

만약 $deq3$ 의 원소가 $0$ 개라면
$deq4$ 의 원소를 $deq3$ 으로 이전해줍니다.

2. 얼음을 녹이는 BFS 함수

이 함수는 하나만 고려해주면됩니다.
$deq$ 에 처음에 모든 물의 위치를 저장한 후
만약 $graph$ 가 얼음이라면
$deq2$ 에 좌표를 추가해줍니다.

이후 $deq$ 의 원소가 $0$ 개라면
$deq2$ 의 원소를 $deq$ 로 이전해줍니다.

✅ 코드에서 주의해야할점

• 백조가 있는 위치도 주위에 얼음이 녹는다.
• 처음 백조의 위치는 방문 처리를 미리 해준다.
• 백조를 찾았는지 판별해주는 $Find$ 변수와 백조를 찾는 $deq3$ 리스트 , 얼음을 녹이면 $deq$ 리스트는 $global$을 통해 전역변수로 선언해줍니다.