문제 정보
- https://www.acmicpc.net/problem/3197
- BFS
- BFS, 분리 집합
문제 정리
Y행 X열 격자에 백조가 두 마리 살고 있다. 호수 얼음으로 덮여 있으며, 매일 물과 맞닿아 있는 얼음이 한 겹씩 녹아 물이 된다. 백조는 물에서만 상하좌우로 이동할 수 있을 때, 두 백조가 만날 수 있는 최소 날짜를 구하는 문제이다.
풀이
이 문제는 얼음이 하루에 한 겹씩 녹음 , 백조가 현재 이동할 수 있는 범위 체크 두 가지 처리를 해줘야 한다.
즉, 빙판BFS, 백조BFS처럼 BFS를 2개 돌리면서 날이 지날 때마다 (백조 이동 처리) -> (빙판 녹이기 처리) -> (날짜 전환) 순서로 진행해주면 된다.
- 두 백조의 초기 위치 파악 및 큐에 초기 상태 저장.
- 두 백조 중 한 백조의 초기 위치를 swanQ에, 초기부터 물이 존재하는 좌표들을 waterQ에 넣는다.
- swanQ에 들어간 백조가 다른 백조를 만날 때까지 3번 ~ 5번 과정을 반복한다.
- swanQ에서 시작해 백조가 오늘 이동 가능한 물 칸을 BFS로 확장한다.
- 오늘 이동 가능한 칸인 경우 swanQ에, 내일 빙판이 녹는 칸인 경우 swanNextQ에 넣는 방식으로 swanQ가 빌 때까지 반복한다.
- waterQ를 기준으로 물과 맞닿아 있는 얼음을 녹인다.
- 오늘 물인 경우 waterQ에, 내일 물이 될 칸인 경우 waterNextQ에 넣는 방식으로 waterQ가 빌 때까지 반복한다.
- waterNextQ에 들어있는 내일 물이 될 칸의 경우 grid의 값을 여기서 갱신해준다.
- 날짜 전환 처리를 해준다.
- swanNextQ의 값을 swanQ로, waterNextQ의 값을 waterQ로 덮어쓴다.
아이디어가 어렵다...
다른 풀이 정리
내 코드가 1200ms 정도 나오고, 파이썬 중 런타임이 빠른 사람의 코드는 600ms정도로 2배 빠르게 나왔다.
또, 태그에 분리 집합이 있었는데, 내 풀이는 분리 집합을 전혀 사용하지 않아서 빠른 코드들이 분리 집합을 사용한 건 아닐까? 라고 생각을 했다.
코드를 분석해보니 분리 집합을 사용한 풀이가 맞았고, 이 방법도 알아두면 좋을 것 같아 큰 흐름만 간단하게 정리했다.
- 처음부터 물 영역을 묶어 라벨링.
- 매일 얼음이 녹아 물이 되면, 해당 칸과 인접한 물 덩어리들을 합침.
- 두 백조가 속한 덩어리가 같은 집합이 되는 순간이 정답.
코드
# 백준 3197
import io
from collections import deque
input = io.BufferedReader(io.FileIO(0), 1<<18).readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def solve(Y, X, grid):
# 백조의 초기 위치 저장
swan = []
for y in range(Y):
for x in range(X):
if grid[y][x] == 'L':
swan.append((y, x))
visited = [[0] * X for _ in range(Y)]
swanQ = deque()
swanNextQ = deque()
waterQ = deque()
waterNextQ = deque()
# 백조와 물의 초기 위치 큐에 추가
swanQ.append(swan[0])
visited[swan[0][0]][swan[0][1]] = 1
for y in range(Y):
for x in range(X):
if grid[y][x] != 'X':
waterQ.append((y, x))
day = 0
while True:
# 백조 이동 BFS
while swanQ:
curY, curX = swanQ.popleft()
for i in range(4):
nextX = curX + dx[i]
nextY = curY + dy[i]
if 0 <= nextX < X and 0 <= nextY < Y and visited[nextY][nextX] == 0:
visited[nextY][nextX] = 1
# 백조를 만난 경우
if nextX == swan[1][1] and nextY == swan[1][0]:
return day
# 다음날 이동 가능한 칸인 경우
if grid[nextY][nextX] == 'X':
swanNextQ.append((nextY, nextX))
# 지금 이동 가능한 칸인 경우
else:
swanQ.append((nextY, nextX))
# 얼음 녹이기 BFS
while waterQ:
curY, curX = waterQ.popleft()
for i in range(4):
nextX = curX + dx[i]
nextY = curY + dy[i]
if 0 <= nextX < X and 0 <= nextY < Y and grid[nextY][nextX] == 'X':
grid[nextY][nextX] = '.'
waterNextQ.append((nextY, nextX))
# 다음날 처리
swanQ = swanNextQ
swanNextQ = deque()
waterQ = waterNextQ
waterNextQ = deque()
day += 1
def main():
Y, X = map(int, input().split())
grid = []
for _ in range(Y):
grid.append(list(input().decode().strip()))
print(solve(Y, X, grid))
main()
