💠 3197 백조의 호수
문제
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.
입력
입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
출력
첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.
분석
처음에는 간단하게 생각하고 얼음을 녹이는 과정과 두 백조가 만나는 과정을 BFS로 구현하여 만날 때까지 확인하는 방식으로 구현하였으나 역시나 시간 초과가 났다. 당연히 R, C가 1500까지 큰 범위라서...(골드도 아니고 플래티넘을 너무 얕본 것 같다...🙈) 모든 범위를 재탐색하는 방법은 시간 초과가 나므로 이미 탐색한 부분에 대해서는 다시 확인해 볼 필요가 없었던 문제다. 분리 집합으로도 풀 수 있다고 하니 나중에 시간이 되면 그 방법으로도 풀어봐야겠다...
이 문제는 백준 게시판의 관련 글을 보고 도움을 얻어 풀었다.
- 먼저 녹인다!
melting()
- water 큐에는 호수의 물의 좌표가 담겨 있다. 탐색을 하면서 물이 아닌 얼음인 부분을 만났다면 water가 아닌 water_tmp 큐에 담는다. 이 큐는 다음 번 탐색 때 사용될 큐이다.
- 두 백조가 만나는지 확인한다!
Is_meet()
- 여기서 사용하는 swan_move 큐에는 초기에 다른 하나의 백조 좌표가 담겨 있고, 마찬가지로 다음 번에 사용할 swan_move_tmp 큐가 있다.
- 만나게 되면 정답을 출력. 아니면 계속 검사
- 계속 검사하게 되면, tmp 큐로 업데이트해준다.
소스 코드
import sys
from collections import deque
input = sys.stdin.readline
r, c = map(int, input().split())
lake = [list(input().strip()) for _ in range(r)]
swan = []
water, water_tmp = deque(), deque()
swan_move, swan_move_tmp = deque(), deque()
visited = [[0 for _ in range(c)] for _ in range(r)]
water_visited = [[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
for j in range(c):
if lake[i][j] == 'L':
swan.append((i, j))
if lake[i][j] == '.' or lake[i][j] == 'L':
water.append((i, j))
water_visited[i][j] = True
lake[swan[0][0]][swan[0][1]] = '.'
lake[swan[1][0]][swan[1][1]] = '.'
visited[swan[0][0]][swan[0][1]] = True
swan_move.append((swan[0][0], swan[0][1]))
def melting():
while water:
x, y = water.popleft()
lake[x][y] = '.'
for nx, ny in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
if nx < 0 or ny < 0 or nx >= r or ny >= c:
continue
if not water_visited[nx][ny]:
if lake[nx][ny] == '.':
water.append((nx, ny))
water_visited[nx][ny] = True
else:
water_tmp.append((nx, ny))
water_visited[nx][ny] = True
def Is_meet():
while swan_move:
x, y = swan_move.popleft()
if x == swan[1][0] and y == swan[1][1]:
return 1
for nx, ny in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
if nx < 0 or ny < 0 or nx >= r or ny >= c:
continue
if not visited[nx][ny]:
if lake[nx][ny] == '.':
swan_move.append((nx, ny))
visited[nx][ny] = True
else:
swan_move_tmp.append((nx, ny))
visited[nx][ny] = True
return 0
days = 0
while True:
melting()
if Is_meet():
print(days)
break
days += 1
swan_move, water = swan_move_tmp, water_tmp
swan_move_tmp = deque()
water_tmp = deque()