[백준] 3197번 : 백조의 호수

3197번: 백조의 호수

3197번: 백조의 호수

🤔 문제분석

구현은 까다롭지 않은 문제이나, 시간복잡도를 최적화 해야한다. 이전에 움직였던 자료를 재 활용하여 이전에 탐색했던 내용을 기반으로 다시 탐색해 나아가야합니다.

문제를 쉽게 풀기 위해, 백조를 움직이는 것과, 빙산이 물이 되는 것을 나누었습니다.

백조를 한번움직이면, 빙산에 도달하기전까지의 이전의 위치를 기록하고 있다가 빙산이 녹고난뒤에 다음에 백조를 움직입니다.

빙산을 녹일때 빙산을 녹인뒤, 다음에 시점에 녹일 빙산은 현재 녹은 빙산임으로 다음에 녹일 빙산의 정보를 다음에 빙산을 녹일 후보로 사용합니다.

📝 의사코드

1. 백조를 움직인다. ( 백조를 다 움직이고 난뒤 마지막의 위치를 기록하고 있다가 다음 움직임에 사용한다. )
   1. 백조끼리 만나면 종료한다.
2. 얼음을 녹입니다. ( 방금 얼음에서 물로된 것들을 기록하고 있다가 다음 시점에 얼음을 녹일 물로 사용합니다. )
3. 시간을 증가 시키고, 1번 2번 사항을 반복합니다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

R, C = map(int, input().split())

table = [list(str(input().strip())) for _ in range(R)]

def move_bird(queue : deque, visited : list):
    new_queue = deque()
    
    while queue:
        y, x = queue.popleft()
        
        if swan[1][0] == y and swan[1][1] == x:
            return True, None
        
        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny, nx = dy + y, dx + x
            if R > ny >=0 and C > nx >= 0 and not visited[ny][nx]:
                visited[ny][nx] = True
                
                if table[ny][nx] == '.':
                    queue.append((ny, nx))
                else:
                    new_queue.append((ny, nx))
                    
    return False, new_queue

def melt(water):
    new_water = deque()
    queue = deque(water)
    
    while queue:
        y, x = queue.popleft()
        
        for dy, dx in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            ny, nx = dy + y, dx + x
            if R > ny >=0 and C > nx >= 0:
                if table[ny][nx] == 'X':
                    table[ny][nx] = '.'
                    new_water.append((ny, nx))
                    
    return new_water

swan = deque()
water = deque()

for i in range(R):
    for j in range(C):
        if table[i][j] == 'L':
            table[i][j] = '.'
            swan.append((i, j))
            water.append((i, j))
        if table[i][j] == '.':
            water.append((i, j))

queue = deque([(swan[0][0], swan[0][1])])

visited = [[False for _ in range(C)] for _ in range(R)]
visited[swan[0][0]][swan[0][1]] = True

day = 0
while True:
    is_found, queue = move_bird(queue, visited)
    if is_found:
        break
    
    water = melt(water)
    day += 1

print(day)

🎯 피드백 및 개선사항

처음에는 데이크스트라로 문제를 해결하려고 했습니다. 물을 만나면 가중치를 0으로 두고, 빙산을 만나면 가중치를 1을 더함으로서 얼음을 녹여갑니다. 시간복잡도로 문제를 해결하지 못하였고, 너비우선탐색으로 문제 해결방향을 고쳤습니다.

너비우선탐색의 동작 및 기본 개념에 대하여 다시한번더 라마인더 하게 되었습니다. 너비우선탐색의 알고리즘의 기본의 원리를 잘 꿰뚫고 있다면 쉽게 풀 수 있을거라고 생각합니다.