Baekjoon-3197-백조의 호수
06 Oct 2022지금까지 항상 List를 Queue로 활용해 왔는데, Collection의 deque 모듈을 사용하는 것이 연산 시간 측면에서 훨씬 유리하다는 것을 알 수 있었다.
ref: https://wellsw.tistory.com/122
import sys
from collections import deque
input = sys.stdin.readline
R,C = map(int, input().split())
maps = []
swan = []
for i in range(R):
line = [c for c in input().strip()]
maps.append(line)
for j,c in enumerate(line):
if c=='L':
swan.append([i,j])
maps[i][j] = '.' # change as ocean
# 방법 1: 얼음 없애고 백조 BFS 반복 -> count 하기
visited = [[0]*C for _ in range(R)]
visited_swan = [[0]*C for _ in range(R)]
def remove_ice(queue):
global visited, maps
new_queue = deque() # removed ice
if len(queue)==0:
# Find all ocean first
for i in range(R):
for j in range(C):
if maps[i][j] == '.' and visited[i][j]==0:
queue.append([i,j])
visited[i][j] = 1
while queue:
x,y = queue.popleft()
for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
if 0<=x+dx<R and 0<=y+dy<C:
if visited[x+dx][y+dy]==0:
if maps[x+dx][y+dy]=='.': # ocean BFS
queue.append([x+dx,y+dy])
else: # removed ice queue for next removal
new_queue.append([x+dx,y+dy])
visited[x+dx][y+dy] = 1
else:
while queue:
x,y = queue.popleft()
for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
if 0<=x+dx<R and 0<=y+dy<C:
if visited[x+dx][y+dy]==0:
if maps[x+dx][y+dy]=='X': # removed ice queue for next removal
new_queue.append([x+dx,y+dy])
visited[x+dx][y+dy] = 1
for x,y in new_queue:
maps[x][y] = '.'
return new_queue
def check_swan(queue):
global visited_swan
if len(queue) == 0:
queue = deque([swan[0]])
visited_swan[swan[0][0]][swan[0][1]] = 1
new_queue = deque()
while queue:
x,y = queue.popleft()
for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
if 0<=x+dx<R and 0<=y+dy<C:
if visited_swan[x+dx][y+dy]==0:
if maps[x+dx][y+dy]=='.':
queue.append([x+dx,y+dy])
visited_swan[x+dx][y+dy] = 1
if x+dx==swan[1][0] and y+dy==swan[1][1]:
return True, []
else:
new_queue.append([x+dx,y+dy])
visited_swan[x+dx][y+dy] = 1
return False, new_queue
queue = deque()
swan_queue = deque()
count = 0
result, swan_queue = check_swan(swan_queue)
while not result:
queue = remove_ice(queue)
count += 1
result,swan_queue = check_swan(swan_queue)
print(count)