백준 3197 백조의 호수

haruponea·2021년 3월 27일
0

BOJ

목록 보기
30/41

문제 링크 https://www.acmicpc.net/problem/3197

풀이
큐를 여러개 사용해야 하는 BFS다. swan, next_swan, water, next_water 큐를 만들어 주고 처음 맵을 순회하면서 물이 있는 칸의 좌표를 water에 넣어준다. 그후 swan_bfs()를 수행하는데 이때 주변 칸을 순회하면서 만나는 경우는 3가지이다.

  1. 다른 백조와 만날 경우
    possible을 True로 바꾸고 함수를 종료한다.
  2. 빙판과 만날 경우
    next_swan큐에 넣어 준다. 다음 bfs때 빙산이 녹아 물이 되는 칸이므로 탐색해야하기 때문
  3. 물과 만날 경우
    swan큐에 물의 좌표를 그대로 넣어준다. 일반적인 bfs상황이다.
    그후 water_bfs()를 수행하는데 인접 칸이 빙판이면 물로 바꾸고 next_water큐에 넣어준다.

그리고 주의할 점은 solution()에서 swanq, waterq를 next_swanq, next_waterq로 바꾸고 next_swanq, next_waterq를 비워야 하는데 pop을 사용해버리면 안된다. swanq, waterq가 각각 next_swanq, next_waterq 와 같은 객체를 가리키기 때문에 swanq, waterq도 비워진다. 따라서 새로운 객체를 할당하자.

Python

from collections import deque
import sys, copy
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
>
n, m = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(n)]
swan = []
swanq = deque()
next_swanq= deque()
waterq = deque()
next_waterq = deque()
vis = [[False] * m for _ in range(n)]
possible = False
>
for i in range(n):
    for j in range(m):
        if board[i][j] == 'L':
            swan = (i, j)
        if board[i][j] != 'X':
            waterq.append((i, j))
def swan_bfs():
    global possible
    while swanq and possible == False:
        x, y = swanq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and vis[nx][ny] == False:
                if board[nx][ny] == 'L':
                    possible = True
                    vis[nx][ny] = True
                    return
                elif board[nx][ny] == '.':
                    swanq.append((nx, ny))
                    vis[nx][ny] = True
                elif board[nx][ny] == 'X':
                    vis[nx][ny] = True
                    next_swanq.append((nx, ny))
>
>
def water_bfs():
    while waterq:
        x, y = waterq.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if board[nx][ny] == 'X':
                    board[nx][ny] = '.'
                    next_waterq.append((nx, ny))
>
>
def solution():
    global swanq, waterq, next_swanq, next_waterq
    day = 0
    swanq.append((swan[0], swan[1]))
    vis[swan[0]][swan[1]] = True
    while(possible == False):
        swan_bfs()
        if possible == False:
            water_bfs()
            swanq = next_swanq
            waterq = next_waterq
            next_swanq = deque()
            next_waterq= deque()
            day += 1
    print(day)
>
>
solution()

0개의 댓글