백준 3197 백조의 호수 (파이썬)

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

3197번: 백조의 호수

문제는 어렵지 않은데 시간 초과를 해결하는 것이 쉽지 않았다. 아래와 같이 풀면 된다

물bfs -> 빙판 칸 물임시큐 저장 -> 백조bfs -> 빙판 칸 백조임시큐 저장 -> 물, 백조 큐를 임시큐로 바꾼다 -> 반복

맨 처음에 백조에 해당하는 칸도 물에 대한 큐에 넣어줘야 하는것을 주의해야한다

 

1. 백조, 물을 각각 저장할 큐와 다음 위치를 저장할 임시 큐 2개씩 총 4개의 큐를 만든다

2. 얼음이 녹는 것을 물이 이동하는 것으로 처리한다. 물에 대한 bfs를 먼저 실행

3. 다음 칸이 빙판이면 다음번 bfs 때 물이 되기 때문에 바로 녹이지 않고 임시큐에 넣는다

4. 현재 상황에서 백조가 이동할 수 있는만큼 이동한다. 다음 칸이 빙판이면 임시큐에 넣는다

5. 백조가 만나지 못하면 물과 백조에 대한 큐를 각각의 임시큐로 치환하고 임시큐를 초기화한다

6. 만날 때까지 과정 반복

from collections import deque
import sys

input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs():
    while q:
        x, y = q.popleft()
        if x == x2 and y == y2:
            return 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not c[nx][ny]:
                    if a[nx][ny] == '.':
                        q.append([nx, ny])
                    else:
                        q_temp.append([nx, ny])
                    c[nx][ny] = 1
    return 0

def melt():
    while wq:
        x, y = wq.popleft()
        if a[x][y] == 'X':
            a[x][y] = '.'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if not wc[nx][ny]:
                    if a[nx][ny] == 'X':
                        wq_temp.append([nx, ny])
                    else:
                        wq.append([nx, ny])
                    wc[nx][ny] = 1

m, n = map(int, input().split())
c = [[0]*n for _ in range(m)]
wc = [[0]*n for _ in range(m)]

a, swan = [], []
q, q_temp, wq, wq_temp = deque(), deque(), deque(), deque()

for i in range(m):
    row = list(input().strip())
    a.append(row)
    for j, k in enumerate(row):
        if a[i][j] == 'L':
            swan.extend([i, j])
            wq.append([i, j])
        elif a[i][j] == '.':
            wc[i][j] = 1
            wq.append([i, j])

x1, y1, x2, y2 = swan
q.append([x1, y1])
a[x1][y1], a[x2][y2], c[x1][y1] = '.', '.', 1
cnt = 0

while True:
    melt()
    if bfs():
        print(cnt)
        break
    q, wq = q_temp, wq_temp
    q_temp, wq_temp = deque(), deque()
    cnt += 1