💻 Problem
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
아래에는 세 가지 예가 있다.
...XXXXXX..XX.XXX ....XXXX.......XX .....XX..........
....XXXXXXXXX.XXX .....XXXX..X..... ......X..........
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X.....
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX....
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX....
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............
..XXXXX...XXX.... ....XX.....X..... .................
....XXXXX.XXX.... .....XX....X..... .................
처음 첫째 날 둘째 날
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는지 계산하는 프로그램을 작성하시오.
- 1 ≤ R, C ≤ 1500.
💡 Approach
문제를 읽었을 때 예전에 풀었던 치즈 문제가 생각났다.
그래서 처음엔 치즈 문제처럼 풀었다.
bfs로 백조 둘이 만날 수 있는지 체크하고, bfs로 모든 물 칸에서 인접한 빙판 녹이고...
import sys
from collections import deque
input = sys.stdin.readline
# 백조들이 만날 수 있는지 확인하기
def can_meet():
queue = deque([swan[0]])
visited = [[False] * C for _ in range(R)]
while queue:
y, x = queue.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 백조 둘이 만났으면 종료
if (ny, nx) == swan[1]:
return True
# 호수 범위 안에 들고 방문한 적이 없는 칸
if 0 <= ny < R and 0 <= nx < C and not visited[ny][nx]:
# 물 칸이면 이어서 탐색하기
if lake[ny][nx] == '.':
queue.append((ny, nx))
visited[ny][nx] = True
return False
# 빙판 녹이기 (하루)
def melt(y, x):
queue = deque([(y, x)])
while queue:
y, x = queue.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 호수 범위 안에 들고 방문한 적이 없는 칸
if 0 <= ny < R and 0 <= nx < C and not visited[ny][nx]:
# 빙하 칸이면 녹이기
if lake[ny][nx] == 'X':
lake[ny][nx] = '.'
visited[ny][nx] = True
# 물 칸이면 이어서 탐색하기
elif lake[ny][nx] == '.':
queue.append((ny, nx))
visited[ny][nx] = True
R, C = map(int, input().split())
lake = [list(input().rstrip()) for _ in range(R)] # 호수 정보
swan = [] # 백조 위치
days = 0 # 백조들이 만나는 데까지 걸리는 날
dy = [-1, 1, 0, 0] # 상하좌우
dx = [0, 0, -1, 1]
# 백조의 위치 찾기
for i in range(R):
for j in range(C):
if lake[i][j] == 'L':
swan.append((i, j))
while True:
# 백조들이 만날 수 있는지 확인하고 만났다면 종료
if can_meet():
print(days)
break
# 빙판 녹이기
visited = [[False] * C for _ in range(R)]
for i in range(R):
for j in range(C):
# 아직 방문하지 않은 물 칸이면 녹이기
if not visited[i][j] and lake[i][j] == '.':
melt(i, j)
days += 1그랬더니 시간 초과..!
위 코드의 문제점은 하루에 두 번 bfs를 돌리는데 매번 방문 배열을 새로 생성하고 전체 격자를 반복한 것이다.
- can_meet(): bfs를 매번 처음부터 새로 수행하고 있음
- melt(): 매번 물 칸 전체를 순회해서 인접한 빙판 칸을 찾고 있음
R, C의 최댓값은 각각 1500이다.
1500 * 1500 배열에서 만약 백조가 (0, 0), (1499, 1499)에 있다고 하면 하루에 대각선으로 한 줄씩 녹으니 약 1500일 정도가 소요될 것이다.
- can_meet()이 1500 * 1500 = 2 * 10^6
- melt()가 1500 * 1500 = 2 * 10^6
이게 1500일 반복한다고 생각하면 1500 * 4 * 10 ^ 6 = 6 * 10 ^ 9
얼추 계산한 거라 계수는 애매하지만 10^9만 생각해도 시간 초과다.
🔨 틀린 코드 최적화
그럼 시간 초과를 해결하기 위해 백조들이 만날 수 있는지 확인하는 함수(can_meet())와 빙하를 녹이는 함수(melt())를 최적화해 보자.
1️⃣ 백조들이 만날 수 있는지 확인하기
현재는 매일 bfs를 처음부터 다시 하고 있었다.
시작 백조 위치부터 bfs를 돌려서 물 칸이면 이동해서 목표 백조 위치까지 이동할 수 있는지 확인했다.
하지만 이렇게 되면 아래의 상황일 때 (1, 1)까지는 이동할 수 있는 걸 알고 있음에도 (0, 1)부터 다시 탐색해야 한다.
| .L .. XX .. .L |
배열의 크기가 클수록 손해 보는 계산이 많을 것이다.
만약 어제 (1, 1)까지 이동할 수 있는 걸 기록해 뒀더라면 (0, 1)에서 시작하지 않고 바로 (1, 1)에서 시작해도 될 것이다.
그래서 큐를 두 개 만들어 오늘 탐색할 큐(cur_swan_q)와 내일 탐색할 큐(next_swan_q)를 나누었다.
오늘 탐색할 큐에는 인접한 물 칸을 넣고, 내일 탐색할 큐에는 인접한 빙하 칸을 넣는다.
탐색하면서 만나는 빙하 칸은 물 칸과 인접한 빙하 칸이기 때문에 내일이면 녹아있을 것이다.
즉, 오늘은 못 갔지만 빙하가 한 칸만 녹으면 내일 갈 수 있는 곳을 저장하는 게 포인트이다.
마찬가지로 방문 배열도 통합해서 관리한다.
여기까지 최적화했을 때는 메모리 초과가 떴다.
2️⃣ 빙하 녹이기
빙하 녹이는 과정도 비슷하다.
현재는 매일 호수의 모든 물 칸을 돌고 있고 방문 배열도 하루마다 초기화하고 있다.
백조들이 만날 수 있는 함수를 최적화한 것처럼 큐를 두 개로 나눠서 물 칸 주변의 빙하 칸만 골라서 녹이도록 한다.
처음에 백조 위치를 찾을 때 물 위치도 같이 찾아서 전부 큐에 넣는다.
큐에 들어있는 물 칸을 전부 탐색하고 빙하 칸을 만나면 다음에 탐색할 물 위치 큐에 삽입한다.
이렇게 최적화해서 통과한 코드가 아래 코드이다.
import sys
from collections import deque
input = sys.stdin.readline
# 백조들이 만날 수 있는지 확인하기
def can_meet():
global next_swan_q
cur_swan_q = next_swan_q
next_swan_q = deque()
# 오늘 이동 가능한 칸만 탐색하기
while cur_swan_q:
y, x = cur_swan_q.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 백조 둘이 만났으면 종료하기
if (ny, nx) == swan[1]:
return True
# 호수 범위 안에 들고 방문한 적이 없는 칸
if 0 <= ny < R and 0 <= nx < C and not swan_visited[ny][nx]:
# 물 칸이면 이어서 탐색하기
if lake[ny][nx] == '.':
cur_swan_q.append((ny, nx))
# 빙하 칸이면 다음에 이동할 큐에 넣기
elif lake[ny][nx] == 'X':
next_swan_q.append((ny, nx))
swan_visited[ny][nx] = True
return False
# 빙판 녹이기 (하루)
def melt():
global next_water_q
cur_water_q = next_water_q
next_water_q = deque()
while cur_water_q:
y, x = cur_water_q.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 호수 범위 안에 들고 방문한 적이 없는 칸
if 0 <= ny < R and 0 <= nx < C and not water_visited[ny][nx]:
# 빙하 칸이면 녹이기
if lake[ny][nx] == 'X':
lake[ny][nx] = '.'
next_water_q.append((ny, nx))
water_visited[ny][nx] = True
dy = [-1, 1, 0, 0] # 상하좌우
dx = [0, 0, -1, 1]
R, C = map(int, input().split())
lake = [list(input().rstrip()) for _ in range(R)] # 호수 정보
swan = [] # 백조 위치
days = 0 # 백조들이 만나는 데까지 걸리는 날
cur_water_q = deque() # 물 칸
next_water_q = deque() # 내일 탐색할 물 칸
water_visited = [[False] * C for _ in range(R)]
# 백조의 위치와 물 위치 찾기
for i in range(R):
for j in range(C):
if lake[i][j] in ('.', 'L'):
if lake[i][j] == 'L':
swan.append((i, j))
next_water_q.append((i, j))
water_visited[i][j] = True
cur_swan_q = deque() # 백조가 오늘 갈 수 있는 칸
next_swan_q = deque([swan[0]]) # 빙하가 오늘 녹으면 백조가 내일 갈 수 있는 칸
swan_visited = [[False] * C for _ in range(R)]
swan_visited[swan[0][0]][swan[0][1]] = True
while True:
# 백조들이 만날 수 있는지 확인하고 만났다면 종료하기
if can_meet():
print(days)
break
# 빙판 녹이기
melt()
days += 1
✏️ Solution
위 코드에서 global을 지우고 함수에서 큐를 return 하도록 정리한 코드이다.
import sys
from collections import deque
input = sys.stdin.readline
# 백조들이 만날 수 있는지 확인하기
def move_swan():
next_swan_q = deque()
# 오늘 이동 가능한 칸만 탐색하기
while cur_swan_q:
y, x = cur_swan_q.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 백조 둘이 만났으면 종료하기
if (ny, nx) == swan[1]:
return True, None
# 호수 범위 안에 들고 방문한 적이 없는 칸
if 0 <= ny < R and 0 <= nx < C and not swan_visited[ny][nx]:
# 물 칸이면 이어서 탐색하기
if lake[ny][nx] == '.':
cur_swan_q.append((ny, nx))
# 빙하 칸이면 다음에 이동할 큐에 넣기
elif lake[ny][nx] == 'X':
next_swan_q.append((ny, nx))
swan_visited[ny][nx] = True
return False, next_swan_q
# 빙판 녹이기 (하루)
def melt_ice():
next_water_q = deque()
while cur_water_q:
y, x = cur_water_q.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
# 호수 범위 안에 들고 방문한 적이 없는 칸
if 0 <= ny < R and 0 <= nx < C and not water_visited[ny][nx]:
# 빙하 칸이면 녹이기
if lake[ny][nx] == 'X':
lake[ny][nx] = '.'
next_water_q.append((ny, nx))
water_visited[ny][nx] = True
return next_water_q
R, C = map(int, input().split())
lake = [list(input().rstrip()) for _ in range(R)] # 호수 정보
dy = [-1, 1, 0, 0] # 상하좌우
dx = [0, 0, -1, 1]
swan = [] # 백조 위치
cur_water_q = deque() # 물 칸
water_visited = [[False] * C for _ in range(R)]
# 초기 위치 찾기
for i in range(R):
for j in range(C):
if lake[i][j] in ('.', 'L'):
if lake[i][j] == 'L':
swan.append((i, j))
cur_water_q.append((i, j))
water_visited[i][j] = True
cur_swan_q = deque([swan[0]]) # 백조가 오늘 갈 수 있는 칸
swan_visited = [[False] * C for _ in range(R)]
swan_visited[swan[0][0]][swan[0][1]] = True
days = 0 # 백조들이 만나는 데까지 걸리는 날
while True:
# 백조들이 만날 수 있는지 확인하고 만났다면 종료하기
can_meet, next_swan_q = move_swan()
if can_meet:
print(days)
break
# 빙판 녹이기
cur_water_q = melt_ice()
# 하루 마무리하기
cur_swan_q = next_swan_q
days += 1처음 코드와 비교했을 때 바꾼 코드는 매일 bfs가 중복으로 반복되는 것이 아니기 때문에 days를 곱하지 않아도 된다.
바꾼 코드의 시간 복잡도는 O(R * C)로 볼 수 있다.
- 5 * R * C + 5 * R * C = 10 * R * C = 10 * 1500 * 1500 = 약 2 * 10^7
'Algorithm > 백준 (BOJ)' 카테고리의 다른 글
| [Python] 백준/BOJ 14929번: 귀찮아 (SIB) (Silver 4) (0) | 2025.07.11 |
|---|---|
| [Python] 백준/BOJ 17086번: 아기 상어 2 (Silver 2) (0) | 2025.07.10 |
| [Python] 백준/BOJ 1655번: 가운데를 말해요 (Gold 2) (0) | 2025.06.28 |
| [Python] 백준/BOJ 24499번: blobyum (Silver 4) (0) | 2025.06.20 |