백준 3197번: 백조의 호수 (Python, PyPy3)

접근

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

3197번: 백조의 호수

문제 자체는 쉬워보이지만 시간 안에 들어가기가 굉장히 빡셌던 문제였다.

핵심은 백조와 얼음이 녹는 과정을 매번 bfs 탐색하는 것이 아니라, 처음에는 bfs 탐색을 하지만, 두번째 부터는 얼음이 녹은 부분, 그리고 백조는 백조가 신규로 갈 수 있는 부분만 탐색하는 것이 중요했다. 그러기 위해 백조 큐, 백조 임시 큐, 물 큐, 물 임시 큐 총 4개의 큐를 이용해서 풀 수 있었다.

문제 해결을 위한 순서는

1. 백조큐에 첫 백조의 위치를 넣고 bfs 탐색을 한다. 이 탐색 중에 백조가 가지 못하는 곳(얼음의 가장자리)를 백조 임시 큐에 넣는다.
2. 물의 위치를 bfs 탐색하고, 마찬가지로 물이 아닌 곳(얼음의 가장자리)를 물 임시 큐에 넣는다.
3. 1에서 구해진 백조 임시 큐를 백조 큐로 옮기고 해당 위치에 대해서만 bfs 탐색을 한다. 이 과정에서 다른 백조를 만나면 코드를 종료한다.
4. 2에서 구해진 물 임시 큐를 물 큐로 옮기고 해당 위치에 대해서만 bfs 탐색을 해서 물이 녹은 후의 새로운 가장자리를 다시 물 임시 큐에 넣는다.

Python으로는 통과 못하고 PyPy3으로 통과하였다.

코드

import sys
from collections import deque


R, C = map(int, sys.stdin.readline().split())
swan = []
matrix = []
sq, sq_t, wq, wq_t = deque(), deque(), deque(), deque()
for i in range(R):
    matrix.append(list(sys.stdin.readline().strip()))
    for j in range(C):
        if matrix[i][j] == "L":
            swan.append((i, j))
            wq.append((i, j))
            matrix[i][j] = 0
        elif matrix[i][j] == ".":
            # 물을 입력받을 때 물 큐에 미리 추가하여 시간을 아낄 수 있다.
            matrix[i][j] = 0
            wq.append((i, j))
        else:
            matrix[i][j] = 1
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
swan_visited = [[0] * C for _ in range(R)]
sr, sc = swan[0]
er, ec = swan[1]


def SwanBFS():
    while sq:
        now_r, now_c = sq.popleft()
        for i in range(4):
            nr = now_r + dr[i]
            nc = now_c + dc[i]
            if nr == er and nc == ec:
                return 0
            if nr < 0 or R <= nr or nc < 0 or C <= nc or swan_visited[nr][nc] == 1:
                continue
            swan_visited[nr][nc] = 1
            # 다음 위치가 물이라면 물 큐에 넣어 탐색을 계속하고, 다음 위치가 얼음이라면 백조가 가지 못하는 얼음의 가장자리이므로 임시 큐에 추가해준다.
            if matrix[nr][nc] == 0:
                sq.append((nr, nc))
            else:
                sq_t.append((nr, nc))
    return 1


def Melt():
    while wq:
        r, c = wq.popleft()
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if nr < 0 or R <= nr or nc < 0 or C <= nc or matrix[nr][nc] == 0:
                continue
            # 물에서 가까운 얼음의 가장자리를 물 임시 큐에 추가해준다.
            wq_t.append((nr, nc))
            matrix[nr][nc] = 0


swan_visited[sr][sc] = 1
sq.append((sr, sc))
ans = 0
while SwanBFS():
    ans += 1
    Melt()
    sq, wq = sq_t, wq_t
    sq_t, wq_t = deque(), deque()
print(ans)

더 생각해 볼 것?

큐를 여러개 쓰는 것에 대한 가닥을 잡고서도 제대로 시간 안에 들어오기 까지 매우 오래 걸렸던 문제였다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!