[DFS/BFS/완전탐색] 2573번 - 빙산(BFS)
[백준] 2573번 - 빙산
풀이 시간: 90분 이내
1) 문제 해결 아이디어
일반적인 BFS문제와는 약간 다른 부분이 있었기 때문에 초반에 BFS로 푸는 것이 과연 효율적인가? 맞나? 싶었던 문제였다. 결국 혼자서 푸는데 성공하긴 했지만 추후 복습이 필요한 문제!
보통의 문제들은 입력받은 정보(graph), 방문여부체크(visited) 2개면 풀이가 가능하지만
이 문제의 경우에는 빙산 녹이기를 한 결과(result)가 추가적으로 필요하다.
Q. 빙산 녹이기를 한 결과(result)를 사용해야하는 이유는?
빙산 녹이기를 한 칸의 결과값은 (기존값 - 상하좌우의 바다(0) 개수) 이다.
여기서 중요한 점은 빙산 한 칸을 녹이기를 한 결과를 바로 graph에 반영해버리면 다음 빙산인 칸이 그 칸과 인접한 칸일 때 문제가 발생한다.
예를 들어, 아래와 같은 상황에서 2의 빙산녹이기를 진행한 결과는 0이다.
하지만 이 결과값(0)을 바로 graph에 반영해버리면 다음 빙산인 4를 빙산 녹이기 할 때 상하좌우의 바다 개수가 3개→4개가 되므로 원래는 1이되어야 맞지만 0이되는 문제가 발생한다.
그러므로 결과값을 저장해 둘 result라는 2차원 리스트를 0으로 초기화하여 생성하고 모든 빙산인 칸에 대해 bfs를 한 후 마지막에 graph에 result값을 대입하여 갱신해야 한다!
Q. 방문 체크(visited)를 꼭 사용해야하는 이유는?
다른 BFS 문제들은 방문 처리를 graph에 바로 해도 문제가 되지 않은 경우가 많지만
이 문제의 경우 graph의 값은 bfs가 끝날 때까지 보존되어야 한다. 위에서 언급한 것과 같이 상하좌우의 바다 개수에 따라 해당 칸의 값이 달라지기 때문에 graph에 바로 방문 처리를 해버리면 값에 오류가 발생하게 된다.
<동작 과정>
1. 방문 여부(visited), 빙산이 녹은 결과(result)를 2차원 리스트 0으로, 빙산 덩어리 개수(cnt)를 0으로, 빙산이 다 녹았는지 여부(melt)를 True로 초기화 생성
2. 빙산 녹이기 1회 수행
2-1. 현재 빙산 상태(graph)에서 가장자리를 제외한 좌표에 대해 빙산(1~10)인 곳에서 bfs()호출, 빙산 덩어리 개수(cnt) 1 증가, 녹지 않은 빙산(melt)가 있으므로 False로 변경
3. 빙산 녹이기 1회 후 빙산이 두 덩어리 이상을 분리되지 않고 다 녹았다면 0 출력
4. 이전 빙산이 2개 이상이면 분리 시간(time) 출력
5. 빙산 녹인 결과(result)를 현재 빙산 상태(graph)에 대입하여 업데이트, 분리 시간(time) 1 증가
Q. 빙산 녹이기를 1회 수행한 후 분리 시간(time)을 바로 증가시키지 않고
이전 빙산 덩어리가 2개 이상이면 분리 시간(time)을 출력하는 이유는?
물론 빙산 녹이기를 수행했으므로 바로 분리 시간(time)을 1증가시키고 빙산 녹인 결과(res)의 빙산 덩어리 개수(cnt)의 값을 계산한 값이 2이상인지 확인하는게 맞다. 하지만 방금 빙산 녹이기를 한 결과의 빙산 덩어리 개수(cnt)는 다음 빙산 녹이기를 진행할 때 bfs를 몇번 수행했는지(cnt)에 의해 알 수 있다. 굳이 그걸 계산하기 위해 bfs를 또 돌릴 필요는 없다!!! 어차피 다음 녹이기를 진행할 때 bfs를 하기 때문에... 그래서 이전 빙산 덩어리(cnt)개수를 먼저 확인한 후 분리 시간(time)은 마지막에 증가시켜준다.
첫번째 오류. 시간초과
1. input() 대신에 sys.stdin.readline()으로 입력받으니 해결되었지만 시간이 4972ms로 너무 오래걸리는 것같았다.
2. python3 대신에 PyPy3로 하니 시간이 4972ms→604ms 로 확 줄었다.
2) 소스코드
import sys
from collections import deque
input = sys.stdin.readline
# BFS
def bfs(x, y):
queue = deque()
# 시작점 삽입, 방문 처리
queue.append((x, y))
visited[x][y] = 1
while queue:
x, y = queue.popleft()
cnt = 0 # 현재좌표 기준 빙산 개수
# 빙산이면 상하좌우 탐색
if(graph[x][y] != 0):
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 범위 내이면
if(0 <= nx < n and 0 <= ny < m):
# 바다 개수 카운트
if(graph[nx][ny] == 0):
cnt += 1
# 빙산이고 방문한적이 없으면 삽입, 방문 처리
if(visited[nx][ny] == 0):
queue.append((nx, ny))
visited[nx][ny] = 1
# 바다개수만큼 빙산 녹이기한 결과값 기록
result[x][y] = max(graph[x][y] - cnt, 0) # 최솟값은 0
n, m = map(int, input().split()) # 세로, 가로
# n * m (0: 바다, 1~10: 빙산)
graph = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
time = 0 # 빙산 분리 시간
while True:
visited = [[0] * m for _ in range(n)] # 방문 여부
result = [[0] * m for _ in range(n)] # 빙산이 녹은 결과
cnt = 0 # 빙산 덩어리 개수
melt = True # 빙산이 다 녹았는지 여부
# 빙산 녹이기 1번(가장자리는 무조건 0이므로 검사X)
for i in range(1, n):
for j in range(1, m):
# 방문하지 않은 빙산이면
if(graph[i][j] != 0 and visited[i][j] == 0):
bfs(i, j)
cnt += 1 # 빙산 덩어리 개수 세기
melt = False # 녹지 않은 빙산 있음
# 빙산이 다 녹았다면 0 출력
if melt:
print(0)
break
# 이전 빙산이 2개이상이었으면 분리 시간 출력
if(cnt >= 2):
print(time)
break
# 빙산 녹이기 결과 업데이트
graph = list(result)
time += 1 # 분리 시간 증가