[백준] 3197 백조의 호수

알고리즘

[백준] 3197 백조의 호수 - 플레 5

swanzzz 2025. 6. 16. 22:11

[오늘의 문제]

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

[오늘의 학습 키워드]

너비 우선 탐색
구현

1. 문제설명

두 마리의 백조가 호수에 살아갈 때 두 마리의 백조가 서로 만나려고 합니다.

그러나 호수를 덮고 있는 얼음이 두 백조가 만나는 것을 방해합니다.

호수가 차례로 녹을 때, 매일 물 공간과 접촉한 모든 빙판이 녹습니다.

며칠이 지나야 백조가 만날 수 있는지 계산하는 프로그램을 작성하시오

[제한사항]

시간 제한 1초
메모리 제한 256MB
1 ≤ R, C ≤ 1500
R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다.
'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

2. 접근방식

문제만 보면 구현 방식 자체는 간단합니다.

백조의 위치를 구한 뒤 시작하는 백조가 종료지점으로 이동하는지 구해주면 되는 문제 입니다.

그 과정에서 백조가 이동가능한지 판단한 후, 이동이 불가능 하면 얼음을 녹여주고 다시 BFS를 반복하고

이를 반복하다 백조가 종료지점 (다른 백조)에 다다르면 그 일 수를 출력해주면 되겠죠

몇가지 고려사항을 작성해 보겠습니다.

백조의 위치는 항상 물이 존재합니다.
얼음이 녹기 위해서는 주변 4방향에 항상 물이 존재해야 합니다.
백조의 다음 이동 위치가 물인 경우 이동이 가능합니다.
백조의 다음 이동 위치가 얼음인 경우 그 얼음은 다음 차례에 녹는 얼음 입니다.
1. 이 말은 해당 위치는 백조가 다음번에 이동 가능하다는 의미 입니다.
얼음을 녹일 때 사용할 visited 와 백조의 이동시 사용할 visited를 구분해 주어야 합니다.

위 5가지 사항을 고려하여 코드를 작성해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def BFS():
    while swan_queue:
        x, y = swan_queue.popleft()

        # 종료 조건
        if (x, y) == end:
            return True

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

            if 0 <= nx < N and 0 <= ny < M:
                if not visited[nx][ny]:
                    # 다음 위치가 물인 경우 이동 가능
                    if lake[nx][ny] == '.':
                        swan_queue.append((nx, ny))
                    # 다음 위치가 얼음인 경우 녹인 후 이동 가능
                    else:
                        next_swan_queue.append((nx, ny))
                    visited[nx][ny] = True
    
    return False    

# 얼음 녹이기
def melt_ice():
    while water_queue:
        x, y = water_queue.popleft()

        # 얼음 녹이기
        if lake[x][y] == 'X':
            lake[x][y] = '.'
        
        # 다음 얼음 찾아서 다음으로 녹일 위치 저장
        # 물인 경우 다음번 얼음 위치 찾기 위해 water_queue에 저장
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 다음 위치가 아직 방문하지 않은 물, 얼음 으로 구분된다.
            if 0 <= nx < N and 0 <= ny < M:
                if not water_visited[nx][ny]:
                    if lake[nx][ny] == 'X':         # 얼음인 경우 다음번에 녹임 -> 물이랑 닿아 있으니
                        ice_queue.append((nx, ny))
                    else:                           # 물의 경우 이동 정보로 저장
                        water_queue.append((nx, ny))
                    water_visited[nx][ny] = True    # 물, 얼음 모두 방문처리

# 입력
N, M = map(int, input().split())
lake = [list(input().strip()) for _ in range(N)]    # 호수 정보
visited = [[False] * M for _ in range(N)]           # 백조의 이동 정보
water_visited = [[False] * M for _ in range(N)]     # 물의 위치

# 백조의 위치, 백조의 이동과 다음 이동, 물의 위치와, 얼음의 위치
swan = []   
swan_queue, next_swan_queue, water_queue, ice_queue = deque(), deque(), deque(), deque()

# 초기 정보 찾기
for i in range(N):
    for j in range(M):
        # 백조의 위치 저장, 백조의 위치는 항상 물
        if lake[i][j] == 'L':
            swan.append((i, j))
            water_queue.append((i, j))
        # 물의 위치 저장 -> 녹여야 한다.
        elif lake[i][j] == '.':
            water_visited[i][j] = True
            water_queue.append((i, j))

start = swan[0]
end = swan[1]
swan_queue.append(start)
# 백조 위치 물로 초기화
lake[start[0]][start[1]] = '.'
lake[end[0]][end[1]] = '.'
visited[start[0]][start[1]] = True

answer = 0

while True:
    melt_ice()  # 얼음 녹이기
    if BFS():   # BFS 탐색 -> True 반환 시 백조가 만날 수 있는 경우
        print(answer)
        break
    # queue 바꿔주기
    swan_queue, water_queue = next_swan_queue, ice_queue
    next_swan_queue, ice_queue = deque(), deque()
    answer += 1

[코드설명]

# 입력
N, M = map(int, input().split())
lake = [list(input().strip()) for _ in range(N)]    # 호수 정보
visited = [[False] * M for _ in range(N)]           # 백조의 이동 정보
water_visited = [[False] * M for _ in range(N)]     # 물의 위치

# 백조의 위치, 백조의 이동과 다음 이동, 물의 위치와, 얼음의 위치
swan = []   
swan_queue, next_swan_queue, water_queue, ice_queue = deque(), deque(), deque(), deque()

# 초기 정보 찾기
for i in range(N):
    for j in range(M):
        # 백조의 위치 저장, 백조의 위치는 항상 물
        if lake[i][j] == 'L':
            swan.append((i, j))
            water_queue.append((i, j))
        # 물의 위치 저장 -> 녹여야 한다.
        elif lake[i][j] == '.':
            water_visited[i][j] = True
            water_queue.append((i, j))

우선 입력을 받아 줍니다.

호수의 크기 정보N, M 을 입력 받아 주고 전체 호수의 정보를 lake에 저장해 줍니다.

백조의 이동 정보와 물이 녹을때 사용될 정보를 저장할 각각의 visited 배열을 생성해 주었습니다.

이제 두 마리의 백조 위치를 저장할 swan 배열과 백조의 이동 정보를 저장한 queue, 물이 녹는 정보를 저장할 water_queue를 생성해주었고

현재 위치에서 이동이 불가능한 얼음을 만날 경우 다음번 queue 이동 정보로 사용하기 위해 next_swan_queue와 ice_queue를 생성해 주었습니다.

백조가 물에서 이동하는 정보를 swan_queue에 저장하는데

백조의 다음번 이동 위치가 얼음인 경우 해당 위치는 하루가 지나 얼음이 녹고 난 뒤 이동이 가능합니다.

그 말은 굳이 중첩 반복문을 다시 탐색하여 백조가 이동 가능한 물의 정보를 일일이 찾아 저장하는 것보다 다음번 이동 위치를 BFS 탐색 중에 같이 저장해 굳이 탐색을 다시 해주지 않아도 됩니다.

모든 queue를 생성하였으니 초기 위치를 찾고 저장해 주어야 합니다.

중첩 반복문을 통해 백조의 위치를 찾아 swan에 저장해 주는데 백조가 있는 곳은 물 입니다.

그 말은 물이 주변에 얼음이 있는지 파악해야 하는 위치이므로 water_queue에 같이 저장해 주었고

모든 물의 위치 정보를 water_queue에 저장하며 중첩 탐색을 피하기 위해 water_visited에 표시해 주었습니다.

start = swan[0]
end = swan[1]
swan_queue.append(start)
# 백조 위치 물로 초기화
lake[start[0]][start[1]] = '.'
lake[end[0]][end[1]] = '.'
visited[start[0]][start[1]] = True

answer = 0

while True:
    melt_ice()  # 얼음 녹이기
    if BFS():   # BFS 탐색 -> True 반환 시 백조가 만날 수 있는 경우
        print(answer)
        break
    # queue 바꿔주기
    swan_queue, water_queue = next_swan_queue, ice_queue
    next_swan_queue, ice_queue = deque(), deque()
    answer += 1

이제 저장한 정보를 바탕으로 적절한 초기화와 코드의 실행이 시작되어야 합니다.

swan에는 두 마리 백조의 위치 정보가 저장되어 있습니다.

한 마리가 다른 한 마리를 만나기만 하면 되니 각각 start 와 end로 구분해 주었고 백조의 위치를 swan에 저장해 두었으니 백조가 있던 곳을 lake에서 물로 바꿔 버립니다.

동시에 백조의 시작 위치를 visited에 표시해 주고 무한 반복을 시작합니다.

우리가 구할 것은 한 마리가 다른 한 마리를 만나는데 걸리는 시간이 필요합니다.

따라서 answer를 0으로 초기화 한 상태에서 무한 반복을 시작합니다.

우선 얼음을 먼저 녹이고, 백조의 이동이 가능한지 살펴 주어야 합니다.

이때 백조의 이동이 완료되면 다음번 이동위치를 가져와야 하는데 이 다음번 이동 위치는 next_swan_queue에 저장해 주게 되죠

이를 swan_queue에 저장해주고 next_swan_queue를 비워주면 됩니다.

동일하게 물의 위치 정보를 water_queue에 저장하고 탐색시 얼음을 만나게 되면 ice_queue에 저장합니다.

이 ice_queue에는 물과 만나는 얼음의 위치가 저장되니 다음번에 녹게 되는 얼음이 됩니다.

이 얼음의 위치 정보를 water_queue에 넘겨주고 ice_queue는 비워주면 한번의 탐색으로 계속해서 BFS 탐색이 가능합니다.

# 얼음 녹이기
def melt_ice():
    while water_queue:
        x, y = water_queue.popleft()

        # 얼음 녹이기
        if lake[x][y] == 'X':
            lake[x][y] = '.'
        
        # 다음 얼음 찾아서 다음으로 녹일 위치 저장
        # 물인 경우 다음번 얼음 위치 찾기 위해 water_queue에 저장
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 다음 위치가 아직 방문하지 않은 물, 얼음 으로 구분된다.
            if 0 <= nx < N and 0 <= ny < M:
                if not water_visited[nx][ny]:
                    if lake[nx][ny] == 'X':         # 얼음인 경우 다음번에 녹임 -> 물이랑 닿아 있으니
                        ice_queue.append((nx, ny))
                    else:                           # 물의 경우 이동 정보로 저장
                        water_queue.append((nx, ny))
                    water_visited[nx][ny] = True    # 물, 얼음 모두 방문처리

얼음은 물과 만나는 위치만 녹을 수 있습니다.

즉 겉 테두리 부터 안쪽으로 1칸씩 녹게 됩니다.

water_queue에는 초기 물의 위치가 저장되어 있는데 두번의 탐색을 막아주기 위해 ice_queue의 정보를 water_queue에 저장해주게 되죠

그럼 이때 water_queue의 위치는 물과 만나있는 얼음의 위치가 되기 때문에 얼음을 우선 녹여주는 것입니다.

가져온 위치가 얼음인 경우 lake에 물로 바꿔주고 4방향 탐색을 통해 얼음과 물을 찾아줍니다.

얼음을 찾게 되면 물과 만나는 얼음이니 다음번에 녹게되는 얼음이라 ice_queue에 저장해주고

물을 찾게되면 이동이 가능한 다음 위치이니 water_queue에 저장해주게 됩니다.

동시에 두 위치는 모두 방문했기 때문에 water_visited에 표시해줍니다.

위 과정을 거치면 주변 테두리 얼음부터 녹기 시작하겠죠

얼음을 녹였으면 백조가 만날 수 있는지 파악해 주어야 합니다.

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def BFS():
    while swan_queue:
        x, y = swan_queue.popleft()

        # 종료 조건
        if (x, y) == end:
            return True

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

            if 0 <= nx < N and 0 <= ny < M:
                if not visited[nx][ny]:
                    # 다음 위치가 물인 경우 이동 가능
                    if lake[nx][ny] == '.':
                        swan_queue.append((nx, ny))
                    # 다음 위치가 얼음인 경우 녹인 후 이동 가능
                    else:
                        next_swan_queue.append((nx, ny))
                    visited[nx][ny] = True
    
    return False

백조의 이동 정보는 swan_queue에 저장되어 있는데

가장 먼저 종료 조건을 살펴 줍니다.

만약 현재 위치가 end -> 다른 한 마리를 만난 경우 더이상 반복을 할 필요가 없고 answer를 출력만 해주면 되죠

그게 아니라면 현재 위치를 기준으로 4방향 탐색을 통해 다음번 이동 가능 위치를 찾아줍니다.

다음번 이동 가능 위치는 물과 얼음으로 구분되는데 물을 만난 경우에는 swan_queue에 넣어 계속해서 이동을 실시해주면 되겠죠

얼음을 만난 경우에 이 위치는 다음번에 녹게 되는 얼음이고 answer가 증가하면 백조가 이동이 가능한 위치가 됩니다.

따라서 next_swan_queue에 넣어 다음번 탐색에 해당 위치부터 탐색이 가능하도록 위치를 저장해 주는 것입니다.

모든 탐색이 종료되었는데 True를 반환하지 못한다면 백조를 만나지 못한 것이므로 False를 반환하게 되고 무한 반복이 유지됩니다.

4. 결과

[회고]

확실히 까다로운 문제 였습니다.

구현의 조건에 시간이 가장 걸렸는데 보통 BFS 1번 탐색이 종료되었을 때 원하는 결과가 출력되지 않는다면 다시 중첩 반복문으로 전체 탐색을 통해 다음번 이동 위치를 queue에 저장하게 됩니다.

그러나 이번 문제의 경우 그런식으로 문제를 풀게되면 무조건 시간초과가 나게 되었습니다.

N, M이 최대 1500이 주어지기에 계속 탐색을 실시하면 무조건 시간 초과가 날수밖에 없었습니다.

그렇기에 이번 문제는 시간 초과와의 싸움 이었습니다.

객관적인 시선으로 문제를 바라볼때 구현의 조건 자체는 크게 어렵지 않습니다. 골드 3에서 골드 2 수준의 문제에서도 전체 배열의 얼음을 녹이고 BFS 탐색을 실시하는 과정을 반복하는 문제들이 많기 때문입니다.

그러나 그런 문제들은 N, M의 최대 범위가 좁고 시간이 길어 시간 초과가 나지 않을 뿐이죠

이번 문제는 한번의 BFS 탐색에서 다음번 이동 위치를 찾아 저장하는게 중요했습니다.

또한 시간을 줄이기 위해서는 visited 배열의 사용도 중요했는데 백조의 이동뿐만 아니라 얼음이 녹는데도 최대 1500 x 1500이 걸릴 수 있어서 중첩탐색을 줄이는게 중요했습니다.

따라서 여러개의 visited 배열과 중첩을 줄이는 조건을 찾고 작성하는게 중요했고 그 과정에서 문제를 푸는데 시간이 오래 걸렸습니다.

조건자체는 쉽게 찾아 우선 코드로 작성하였고 중간 중간 코드를 수정하며 시간을 줄이는 방법을 찾아 나갔고 결국에는 문제를 풀 수 있었죠

다음에도 비슷한 문제를 해결하며 학습을 이어 나가겠습니다.