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

 

문제

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

---

문제 설명

1.   R*C 크기의 호수 배열이 주어진다.
   1. 배열 내 두 마리의 백조가 'L'로 주어진다.(백조가 있는 위치도 물이라고 판단한다.)
   2. 배열 내 빙판 공간이 'X'로 주어진다.
   3. 배열 내 물 공간이 '.'으로 주어진다.
2. 두 마리의 백조는 물 공간에서만 이동이 가능하다.
3. 1일이 지날 때 마다 물과 인접한 빙판이 녹는다. 
4. 두 백조가 서로 만나기 위해 몇 일이 걸리는지 구한다.

 

---

풀이

1. 1일차가 지나기 전 현재 물과 인접해 있는 빙판 위치를 탐색하여 Queue에 저장한다.
2. 해당 위치를 기반으로 너비 우선 탐색을 진행하여 현재 빙판이 몇 일이 걸리는 지 계산한다.
   1. 이 때 다음 빙판까지 걸리는 일 수가 더 적을 때만 일 수를 갱신한다.
3.  1일차부터 최악의 경우일 때 나올 수 있는 최대 일 수까지 하루씩 늘려, 탐색의 범위를 키우며, 너비 탐색한다.
   1. n일차에 백조 두 마리가 만날 수 있다면 현재 일차를 반환하고 반복문을 종료한다.
   2. 이 때 다음 날에 방문해야 하는 위치를 두 번째 Queue에 담아 BFS가 종료될 때 해당 Queue를 반환하여 다음 날 탐색 시 다음 날 탐색해야하는 빙판들의 위치가 담겨있는 Queue를 바로 사용하도록 한다.
4. 결과를 출력한다.

---

코드

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

R,C = map(int,input().split())

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

INF = sys.maxsize
board = [list(input().strip()) for _ in range(R)]
dist = [[INF for _ in range(C)] for _ in range(R)]

se = []
queue = deque()

for r in range(R):
    for c in range(C):
        if board[r][c] in ['.','L']:
            if board[r][c] == 'L':
                se.append((r,c))
            queue.append((r,c,0))
            dist[r][c] = 0
        

while queue:
    y,x,cost = queue.popleft()
    
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if ny < 0 or ny > R-1 or nx < 0 or nx > C-1:
            continue
        if dist[ny][nx] <= cost+1:
            continue
        if board[ny][nx] == 'X':
            dist[ny][nx] = cost + 1
            queue.append((ny,nx,cost+1))


def bfs(day):
    queue2 = deque()
    while queue:
        y,x,crnt_day = queue.popleft()

        if (y,x) == (se[1][0],se[1][1]):
            return queue,day
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if ny < 0 or ny > R-1 or nx < 0 or nx > C-1 or visited[ny][nx]:
                continue
            if dist[ny][nx] == day + 1:
                queue2.append((ny,nx,dist[ny][nx]))
                visited[ny][nx] = 1
            if dist[ny][nx] <= day:
                queue.append((ny,nx,dist[ny][nx]))
                visited[ny][nx] = 1
    return (queue2,-1)

day = 0
visited = [[0 for _ in range(C)] for _ in range(R)]
queue = deque([(se[0][0],se[0][1],0)])
visited[se[0][0]][se[0][1]] = 1

while day <= R*C:
    queue,res = bfs(day)
    if res > -1:
        print(res)
        break
    day+=1

---

시간복잡도

• 1일차가 시작되기 전, BFS를 탐색할 때 약 $O(4*R*C) = O(R*C)$정도 소요된다.
• 1일차부터 최대 일 수 까지 BFS를 통해 탐색할 때, 언뜻보면 R*C회 만큼 BFS를 돌리기 때문에
  R*C*(4*R*C)로 오해할 수 있다. 하지만 실제로는 day를 탐색할 때 마다 그 날에 탐색한 위치들을 방문처리 하기 때문에, 최악의 경우 배열을 전체 도는 R*C 만큼의 시간만 소요된다.
• *참고로 최대 일 수는 $log_2{R*C} = log_2{2250000} =$ 21.xxxxx로 21일차 정도로 예상이 가능하다.