# BOJ - 3197 - 백조의 호수

Updated:

``````import sys
from collections import deque

def BFS(water, swan, W, H, lake):
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

endX, endY = swan.pop()

time = 1
while swan:
temp = deque()
while water:
x, y = water.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < H and 0 <= ny < W:
if lake[nx][ny] == 'X':
lake[nx][ny] = '.'
temp.append((nx, ny))
water = temp

temp = deque()
while swan:
x, y = swan.popleft()

if x == endX and y == endY:
return time

if lake[x][y] == 'L':
lake[x][y] = time

for i in range(4):
nx = x + dx[i]
ny = y + dy[i]

if 0 <= nx < H and 0 <= ny < W:
if lake[nx][ny] == '.' or lake[nx][ny] == 'L':
lake[nx][ny] = time
swan.append((nx, ny))
temp.append((nx, ny))
swan = temp
time += 1
return time

def solution():
lake = []
water = deque()
swan = deque()

for _ in range(H):

for i in range(H):
for j in range(W):
if lake[i][j] == "L":
swan.append((i, j))
water.append((i, j))
elif lake[i][j] == ".":
water.append((i, j))

print(BFS(water, swan, W, H, lake))

solution()
``````

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

Categories:

Updated: