[백준] # 3197. 백조의 호수 (파이썬)

문제 링크

 

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

3197번: 백조의 호수

 

문제 내용

 

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는지 계산하는 프로그램을 작성하시오.

 

입력

 

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

 

출력

 

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

IDEA

 

check : 백조가 서로 만나는지 확인하는 함수

melt : 시간이 지날 때마다 빙하가 녹게 하는 함수

swan의 이동 가능한 위치를 저장하는 큐와 업데이트에 필요한 임시 큐 2개, 물인 곳을 저장하는 큐와 업데이트에 필요한 임시 큐 2개 해서 총 4개의 큐를 활용한다.

두 개의 함수에 각각 bfs를 적용하여 탐색하며, 한 턴이 끝날 때마다 큐를 업데이트해준다.

 

CODE

 

# 3197. 백조의 호수 - 플레티넘 5
# 블로그 참고 ㅠ
from collections import deque
dx,dy = (0,1,0,-1), (1,0,-1,0)
# 백조가 서로 만나는지 확인하는 함수
def check():
    while sq:
        x,y = sq.popleft()
        if (x,y) == (x2,y2):
            return True
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if swan_arr[nx][ny] == 0:   # 백조가 방문 안했다면,
                    if arr[nx][ny] == "X":  # 방문할 곳이 빙하이면,
                        sq_temp.append((nx,ny)) # 다음 시간에 녹아 없어지므로 백조가 갈수 있기에 sq_temp에 임시 저장.
                    else:   # 방문할 곳이 물인데 아직 방문 안했다면,
                        sq.append((nx,ny))  # 백조가 이번 시간내에 방문할 수 있도록 sq에 저장.
                    swan_arr[nx][ny] = 1 # 미리 이동한 티 내줘야 이번 시간내에 중복이 일어나지 않는다.
    return False
# 시간이 지날 때마다 빙하가 녹게 하는 함수
def melt():
    while wq:
        x,y = wq.popleft()
        if arr[x][y] == "X":
            arr[x][y] = "." # 빙하가 왔으면 녹여준다.
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if water_arr[nx][ny] == 0:  # 물인데 방문 안했거나, 빙하일 경우 탐색.
                    if arr[nx][ny] == "X": # 방문할 곳이 빙하이면
                        wq_temp.append((nx,ny)) # 다음 시간에 녹아 물이 되므로 wq_temp에 임시 저장.
                    else: # 방문할 곳이 물인데 아직 방문 안했다면,
                        wq.append((nx,ny))
                    water_arr[nx][ny] = 1 # 방문 했으므로 1로 변경.
r,c = map(int,input().split())
sq, sq_temp = deque(), deque()  # swan(백조)의 이동가능한 위치 저장
wq, wq_temp = deque(), deque()  # 물인 곳 저장.
arr = []    # 호수를 그대로 저장. 대신 백조(L)는 물(.)로 변경.
swan = []   # 백조 위치 저장
water_arr = [[0]*c for _ in range(r)] # 물 bfs시에 물일 때 1 저장. 이미 1이면 다음 시간에 굳이 방문 안하도록 설정 가능.
swan_arr = [[0]*c for _ in range(r)] # 백조의 방문 여부를 저장
for i in range(r):
    input_list = list(input().strip())
    arr.append(input_list)
    for j in range(c):
        if input_list[j] == "X":
            continue
        else:
            wq.append((i,j))
            water_arr[i][j] = 1
            if input_list[j] == "L":
                swan.append((i,j))
time = 0
(x1,y1),(x2,y2) = swan
sq.append((x1,y1))
swan_arr[x1][y1] = 1

while True:
    melt()
    if check():
        print(time)
        break
    time += 1
    wq, sq = wq_temp, sq_temp
    wq_temp, sq_temp = deque(), deque()

 

사용 알고리즘

 

BFS

 

풀이 평

 

난이도가 플레티넘인 만큼 풀어봤던 BFS/DFS문제 중에 가장 어려웠다. 큐를 4개를 사용할 생각을 전혀 하지 못했다.. 블로그를 찾아가며 공부한 후 다시 풀었다.