[Baekjoon] 백조의 호수(python)

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

문제 접근

아주 단순한 구현문제인 줄 알았다.

그래서 백조끼리 만날 수 있는지 검사하는 함수와 물의 가장자리에 붙어있는 얼음을 녹이는 함수 두 개만 짜면 되는 줄 알았다.

문제에 테스트케이스가 모두 정답이 되어 제출해봤는데 역시는 역시인가..

 

 

처음 문제를 풀었던 방식은 이렇다.

 

1) 백조끼리 만날 수 있는지 BFS를 통해 검사

2) lake 배열을 매번 체크하면서 물의 가장자리에 있는 얼음을 녹임

 

<오답 코드>

def is_can_meet_swan():

    visited = [[False] * C for _ in range(R)]

    start_x, start_y = swans[0]
    end_x, end_y = swans[1]

    q = deque()

    q.append([start_x, start_y])

    while q:
        x, y = q.popleft()

        if x == end_x and y == end_y:
            return True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (
                nx < 0
                or nx >= R
                or ny < 0
                or ny >= C
                or visited[nx][ny]
                or lake[nx][ny] == "X"
            ):
                continue

            visited[nx][ny] = True
            q.append([nx, ny])

    return False

def melt():
    tmp = [lake[i][:] for i in range(R)]

    for i in range(R):
        for j in range(C):
            if lake[i][j] != ".":
                continue

            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]

                if nx < 0 or nx >= R or ny < 0 or ny >= C or lake[nx][ny] != "X":
                    continue

                tmp[nx][ny] = "."

    return tmp

"""
    생략
"""

처음엔 BFS를 실행할 때 파이썬의 리스트를 이용하여 구현한 것이 시간초과의 원인이라고 생각하여 deque로 변경하여 풀어보았지만 시간초과를 피할 수 없어서 검색을 통해 매번 백조가 서로 만날 수 있는지 체크하고 물의 가장자리 위치를 구하는 방법은 절대 통과할 수 없다는 풀이인 것을 알고 다음에 탐색할 위치와 물의 위치를 미리 저장하여 처리하도록 구현하였다.

---

풀이 과정

먼저 백조가 서로 만날 수 있는지 검사하는 함수를 구현해보자.

def is_can_meet_swan():
    while q:
        x, y = q.popleft()

        if x == end_x and y == end_y:
            return True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= R or ny < 0 or ny >= C or visited[nx][ny]:
                continue

            visited[nx][ny] = True

            if lake[nx][ny] == ".":
                q.append([nx, ny])
            else:
                next_q.append([nx, ny])
    return False

원래는 1번 백조와 2번 백조 위치까지 처음부터 BFS를 통해 탐색하는 구조였다.

 

하지만 물이 아닌 지점에서 탐색이 멈추게 되는데 이때 그냥 버리는 것이 아니라 다음에 탐색할 큐에 저장하는 것이다.

 

즉, 매번 1번 백조부터 2번 백조까지 탐색하는 것이 아니라 지난 탐색 때 얼음에 의해 탐색이 중단되었던 지점부터 다시 탐색하도록 하는 것이다.

 

그 이유는 얼음에 의해 탐색이 중단되었던 지점이 물의 가장자리일 것이고, 이번에는 물이 되었을 것이기 때문이다.

 

 

그 다음으로 얼음을 녹이는 함수를 구현해보자.

def melt():
    while water:
        x, y = water.popleft()

        if lake[x][y] == "X":
            lake[x][y] = "."

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= R or ny < 0 or ny >= C or water_checked[nx][ny]:
                continue

            if lake[nx][ny] == "X":
                next_water.append([nx, ny])
            else:
                water.append([nx, ny])

            water_checked[nx][ny] = True

melt() 함수는 처음에 물의 위치를 모두 큐에 저장한다. 그리고 다음에 탐색할 큐에는 근접한 얼음을 넣어주면 된다.

핵심은 물의 위치들을 매번 구하는 것이 아니라 미리 저장하고 다음에 물이 될 얼음의 위치를 미리 구하여 저장하는 것이다.

 

이렇게 하여 시간초과를 해결할 수 있었다.

 

정말 어려운 문제였던 것 같다....

 

---

정답 코드

"""
    백준 3197번 백조의 호수
"""

import sys
from collections import deque


def is_can_meet_swan():
    while q:
        x, y = q.popleft()

        if x == end_x and y == end_y:
            return True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= R or ny < 0 or ny >= C or visited[nx][ny]:
                continue

            visited[nx][ny] = True

            if lake[nx][ny] == ".":
                q.append([nx, ny])
            else:
                next_q.append([nx, ny])
    return False


def melt():
    while water:
        x, y = water.popleft()

        if lake[x][y] == "X":
            lake[x][y] = "."

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= R or ny < 0 or ny >= C or water_checked[nx][ny]:
                continue

            if lake[nx][ny] == "X":
                next_water.append([nx, ny])
            else:
                water.append([nx, ny])

            water_checked[nx][ny] = True


R, C = list(map(int, sys.stdin.readline().split()))
lake = []
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

for _ in range(R):
    lake.append(list(sys.stdin.readline()[:-1]))

result = 0

# 백조 위치 저장
swans = []

q, next_q, water, next_water = deque(), deque(), deque(), deque()
visited = [[False] * C for _ in range(R)]
water_checked = [[False] * C for _ in range(R)]


for i in range(R):
    for j in range(C):
        if lake[i][j] == "L":
            swans.append([i, j])
            lake[i][j] = "."

        # 물의 위치 저장 -> 백조도 물로 간주한다.
        if lake[i][j] != "X":
            water.append([i, j])
            water_checked[i][j] = True

start_x, start_y = swans[0]
end_x, end_y = swans[1]

q.append([start_x, start_y])

while True:
    melt()

    if is_can_meet_swan():
        break

    q, water = next_q, next_water
    next_q, next_water = deque(), deque()

    result += 1

print(result)