3197: 백조의 호수

문제 링크

3197: 백조의 호수

구현 방식

• 시간 초과를 해결하기 위해 임시 큐를 사용하는 아이디어를 참고했다

• 전반적인 흐름은 While문을 돌면서,
  1) 얼음을 한 타임 녹임 (물에 해당하는 좌표들에서 bfs 한 타임 실행)
  2) 백조 한 타임 이동 (백조에 해당하는 좌표들에서 bfs 한 타임 실행)
  을 시행해주면 된다

• 1)은 melt()를 통해 구현해주었다

  • 만약 다음 칸(board[nx][ny])이 얼음이라면 해당 노드를 물 임시 큐에 넣어준다
  • 만약 다음 칸이 물이라면 해당 노드를 물 큐에 넣어준다

• 2)은 move()를 통해 구현해주었다

  • 만약 다음 칸(board[nx][ny])이 얼음이라면 해당 노드를 백조 임시 큐에 넣어준다
  • 만약 다음 칸이 물이라면 해당 노드를 백조 큐에 넣어준다

• While문에서 1), 2)를 진행한 결과 백조가 만났다면 break하고 answer를 출력

• While문에서 1), 2)를 진행한 결과 백조가 만나지 못했다면 물 큐를 물 임시 큐로 swap, 백조 큐를 백조 임시 큐로 swap하고, 물 임시 큐와 백조 임시 큐를 초기화

코드

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def melt():
    while wqueue:
        x, y = wqueue.popleft()
        if board[x][y] == 'X': board[x][y] = '.'
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<R and 0<=ny<C:
                if not wvisit[nx][ny]:
                    if board[nx][ny] == 'X':
                        wvisit[nx][ny] = True
                        wqueue_tmp.append((nx, ny))
                    else:
                        wvisit[nx][ny] = True
                        wqueue.append((nx, ny))

def move():
    while squeue:
        x, y = squeue.popleft()
        if (x, y) == (d_x, d_y): return True
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx<R and 0<=ny<C:
                if not svisit[nx][ny]:
                    if board[nx][ny] == '.':
                        svisit[nx][ny] = True
                        squeue.append((nx, ny))
                    else:
                        svisit[nx][ny] = True
                        squeue_tmp.append((nx, ny))
    return False


R, C = map(int, sys.stdin.readline().strip().split())
board = [list(sys.stdin.readline().strip()) for r in range(R)]

swan = []
squeue = deque(); squeue_tmp = deque(); wqueue = deque(); wqueue_tmp = deque()
svisit = [[False]*C for r in range(R)]; wvisit = [[False]*C for r in range(R)]
for i in range(R):
    for j in range(C):
        if board[i][j] == 'L':
            wqueue.append((i, j))
            swan.append((i, j))
        elif board[i][j] == '.':
            wqueue.append((i, j))
            wvisit[i][j] = True

s_x, s_y, d_x, d_y = swan[0][0], swan[0][1], swan[1][0], swan[1][1]
squeue.append((s_x, s_y)); svisit[s_x][s_y] = True
board[s_x][s_y] = '.'; board[d_x][d_y] = '.'

answer = 0
while True:
    melt()
    if move(): break
    squeue, wqueue = squeue_tmp, wqueue_tmp
    squeue_tmp, wqueue_tmp = deque(), deque()
    answer += 1
print(answer)