[플레티넘 5] 백준 3197 - 백조의 호수 (파이썬)

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

풀이

백조의 호수 문제는 BFS를 통해서 풀이가 가능하다.

• 문제에서 요구하는 조건은 호수에 얼음이 덮여있다.
• 얼음으로 뒤덮인 호수에 백조 두 마리가 있음
• 물은 백조가 지나갈 수 있지만 얼음은 못 감
• 매일 얼음이 물과 접촉한 부분부터 녹음
• 두 백조가 만날 수 있는 최소 날짜를 구하는 문제

1. 입력 처리 및 초기 세팅을 진행

R, C = map(int, input().split())
A = [list(input()) for _ in range(R)]

R, C와 맵을 2차원 리스트로 저장한다.

1. 백조 위치 탐색

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

백조는 두 마리뿐이므로 처음 두 개의 L 위치를 저장

1. 현재 물의 위치를 저장

for i in range(R):
    for j in range(C):
        if A[i][j] != "X":
            water.append((i, j))
            visit_water[i][j] = True

현재 얼음이 아닌 모든 위치(. or L)를 water 큐에 넣어 얼음 녹이는 기준으로 사용한다.

1. 백조 이동 BFS를 준비한다.

swan_q.append(swan_1)
visit_swan[swan_1[0]][swan_1[1]] = True

한 백조의 위치에서 BFS를 시작해, 다른 백조에게 도달 할 수 있는지 확인한다.

1. 백조 이동 함수

def swan_move():
    while swan_q:
        x, y = swan_q.popleft()
        ...
        if (nx, ny) == swan_2:
            return True

• 현재 백조가 이동 할 수 있는 영역을 탐색한다.
• 갈 수 없는 얼음은 next_swan_q에 넣어서 다음 날 BFS 대상 큐로 저장한다.
• 목표 백조에 도달하면 True를 반환한다.

1. 얼음 녹이기 함수

def melt():
    for _ in range(len(water)):
        ...
        if A[nx][ny] == 'X':
            A[nx][ny] = '.'
            water.append((nx, ny))

• 현재 물과 인접한 얼음(X)을 하루치만 녹여서 .로 바꾸고, 새로 녹은 부분을 물 큐에 넣는다.

1. 시뮬레이션 루프를 진행한다.

day = 0
while True:
    if swan_move():
        print(day)
        break
    melt()
    swan_q, next_swan_q = next_swan_q, deque()
    day += 1

• swan_move()로 백조가 만날 수 있는지 확인한다.
• 안되면 melt()로 얼음 녹이고, day를 하루 증가한다.
• 두 백조가 만나는 날이 정답이다.

시간 복잡도 분석

• 전체 격자당 매일 한 번씩 BFS → O(R * C * T)
• T는 만나는 날까지의 일수인데, 얼음이 모두 녹는 날 이하이므로 최악의 경우 R * C

코드

# 백준 3197 - 백조의 호수
# 분류 : BFS
# 문제집 : 단기간 성장 - 3번
 
R, C = map(int, input().split())
A = [list(input()) for _ in range(R)]
 
# 1. 백조 위치 확인
swans = []
for i in range(R) :
    for j in range(C) :
        if A[i][j] == "L" :
            swans.append((i, j))
        if len(swans) == 2 :
            break
    if len(swans) == 2 :
        break
 
swan_1, swan_2 = swans
 
# 2. 현재 물 찾기
from collections import deque
 
water = deque()
visit_water = [[False] * C for _ in range(R)]
 
for i in range(R) :
    for j in range(C) :
        if A[i][j] != "X" :
            water.append((i, j))
            visit_water[i][j] = True
 
# 3. 백조 이동 BFS 준비
swan_q = deque()
next_swan_q = deque()
visit_swan = [[False] * C for _ in range(R)]
swan_q.append(swan_1)
visit_swan[swan_1[0]][swan_1[1]] = True
 
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def swan_move() :
    while swan_q :
        x, y = swan_q.popleft()
        for dx, dy in directions :
            nx, ny = x + dx, y + dy
            if not (0 <= nx < R and 0 <= ny < C) :
                continue
            if visit_swan[nx][ny] == True :
                continue
            visit_swan[nx][ny] = True
            if (nx, ny) == swan_2 :
                return True
            if A[nx][ny] == '.' :
                swan_q.append((nx, ny))
            elif A[nx][ny] == 'X' :
                next_swan_q.append((nx, ny))
    return False
 
def melt() :
    for _ in range(len(water)) :
        x, y = water.popleft()
        for dx, dy in directions :
            nx, ny = x + dx, y + dy
            if not (0 <= nx < R and 0 <= ny < C) :
                continue
            if visit_water[nx][ny] :
                continue
            if A[nx][ny] == 'X' :
                A[nx][ny] = '.'
                water.append((nx, ny))
                visit_water[nx][ny] = True
 
# 4. 시뮬레이션
day = 0
while True :
    if swan_move() :
        print(day)
        break
    melt()
    swan_q, next_swan_q = next_swan_q, deque()
    day += 1