"정사각형 모양의 4변 중에서 적어도 2변 이상이 외부의 공기와 접촉했을 때 정확히 한 시간 만에 녹아 없어져 버린다."
위의 문장이다. 위의 문장을 통해서 어떤 알고리즘을 사용해야 하는지, 그리고 어떤 논리를 짜야 하는지를 잘 간파해야 이 문제를 어려움 없이 풀 수가 있다.
이 문제를 푸는 방법은 하나의 시뮬레이션 코드를 작성을 해야 한다. 가장 먼저 "외부의 공기"가 너비 우선 탐색을 진행하도록 하고, 그 외부의 공기가 얼음과 부딪히는 횟수를 계산하고, 두 면 이상이 접촉하는 얼음을 기록한 후 그 얼음을 1시간 후에 녹이도록 한다. 그리고 1시간 후에 얼음이 녹은 후 다시 또 너비 우선 탐색을 진행하는 방식으로 코드를 짜면 되는데, 이 코드가 끝마치는 조건은 얼음이 하나도 없을 경우에 해당한다.
이러한 시뮬레이션 코드를 이제 하나하나 작성해보도록 하자.
import sys
from collections import deque
N, M = map(int, input().split())
env = []
for _ in range(N):
env.append(list(map(int, sys.stdin.readline().split())))
visit_counts = [[0 for _ in range(M)] for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
우선 가장 먼저 N과 M을 받아들여 N과 M이라는 각각의 변수에 저장하고, 동계 테스트 센터라는 그 환경을 담을 변수 env를 준비한 후 입력값들을 넣어준다. 그 환경의 각각의 위치에 방문한 횟수를 저장하는 변수 visit_counts 를 준비한다. 마지막으로 너비 우선 탐색을 진행하기 위해서 위 (dx=0, dy=1), 아래 (dx=0, dy=-1), 오른쪽 (dx=1, dy=0), 왼쪽 (dx=-1, dy=0)으로 이동하도록 도와주는 리스트 dx와 dy를 준비해준다.
def bfs():
queue = deque()
# 문제에서 맨 가장자리에는 얼음이 놓이지 않는다고 했으니 [0,0]은 얼음이 없으므로
# 이 부분에서 시작하도록 한다.
init = [0,0]
queue.append(init)
visit_counts[0][0] = 1
# BFS을 통해 외부 공기에 접촉한 얼음에 대한 계산 진행
while queue:
x,y = queue.popleft()
for i in range(len(dx)):
# 위치 이동
new_x = x + dx[i]
new_y = y + dy[i]
if (0 <= new_x < M) and (0 <= new_y < N):
# 이동한 곳에 얼음이 있을 경우
if env[new_y][new_x] == 1:
# 방문 횟수를 1씩 누적
visit_counts[new_y][new_x] += 1
# 이동한 곳에 얼음이 없을 경우
elif (env[new_y][new_x]==0):
# 그 위치가 들리지 않은 곳일 경우에만 이동한다.
if (visit_counts[new_y][new_x] == 0):
# 방문 횟수를 1로 고정
visit_counts[new_y][new_x] = 1
# 얼음이 없는 쪽으로 이동한 곳은 결국 외부 공기와 접촉하는 다른 한 공간이 됨.
queue.append([new_x, new_y])
그리고 나서 너비 우선 탐색(Breadth-first search) 코드를 작성을 해준다.
너비 우선 탐색은 자료구조 큐(Queue)를 사용하기 때문에 파이썬 내장 클래스인 collections 안의 deque를 통해 큐를 생성해준다. 그리고 문제에서 환경의 가장 자리에는 무조건 얼음이 없다고 했으므로 가장자리인 x=0, y=0인 위치부터 너비 우선 탐색을 진행한다.
그 후 큐 안에 데이터가 없어질 때까지 너비 우선 탐색을 진행하는데, 여기서 아래의 조건을 넣어준다.
if (0 <= new_x < M) and (0 <= new_y < N):
0. 새로운 위치의 x의 위치가 0과 M 사이일 때, 그리고 y의 위치가 0과 N 사이일 때만 탐색을 진행하도록 해준다.
이 조건을 통해서 유효한 움직임에 대해서만 탐색이 진행하도록 규제해줄 수 있다.
그리고 아래의 다른 필요한 조건들도 넣어준다.
1. 만약 새로운 위치에 얼음이 있을 경우 얼음의 방문 횟수를 하나씩 누적하고, 새로운 위치에 얼음이 아닐 경우는 방문 횟수를 1로 고정해준다.
2. 너비 우선 탐색의 이동 과정에 있어서 새로운 위치에 얼음이 있을 경우는 그 위치를 queue에 넣어주지 말고, 얼음이 없고 방문한 적이 없을 경우에만 queue에 넣어준다.
if env[new_y][new_x] == 1:
# 방문 횟수를 1씩 누적
visit_counts[new_y][new_x] += 1
elif (env[new_y][new_x]==0):
# 그 위치가 들리지 않은 곳일 경우에만 이동한다.
if (visit_counts[new_y][new_x] == 0):
# 방문 횟수를 1로 고정
visit_counts[new_y][new_x] = 1
# 얼음이 없는 쪽으로 이동한 곳은 결국 외부 공기와 접촉하는 다른 한 공간이 됨.
queue.append([new_x, new_y])
위 조건들을 통해서는 새로운 위치에 얼음이 있을 경우는 방문 횟수를 하나하나 계속 누적하도록 해주고, 얼음이 없을 경우는 방문 횟수를 1로 고정해주고, 유효한 탐색만 큐에 넣어주는 작업을 진행해준다. 이 1번 조건과 2번 조건의 통합을 통해서 유효한 탐색의 조건 하에 두 면 이상이 접촉하는 얼음을 판단해줄 수 있는 논리를 만들어줄 수 있다.
# 모든 방문 시뮬레이션을 마친 후 외부 공기에 의해 접촉한 횟수가 2 이상일 경우 얼음을 녹인다.
for y in range(N):
for x in range(M):
if visit_counts[y][x] >= 2:
env[y][x] = 0
그리고 마지막으로 방문 횟수가 2 이상인 경우 그 얼음을 얼음이 아닌 경우로 바꿔준다.
따라서 위의 코드들을 통해서 얼음의 접촉면에 의해서 녹는 딱 한시간 동안의 시뮬레이션을 진행할 수 있다.
time = 0 # 타이머
while True:
# 만약 얼음이 다 녹았을 경우 (그 경우 env는 0이 M개로 이루어진 리스트가 N개가 된다.)
# 이 부분은 무조건 앞에 두어야 한다. 그래야만 초기 값으로 모두 0이 주어진 경우에 불필요한 bfs를 진행하지 않게 됨.
if (env.count([0 for _ in range(M)]) == N):
break
visit_counts = [[0 for _ in range(M)] for _ in range(N)]
bfs()
time += 1
# 걸린 시간을 출력해준다.
print(time)
마지막으로 이 시뮬레이션을 모든 얼음이 다 녹을 때까지 계속 진행을 해주고, 모든 얼음이 녹았을 때 while 루프를 끝내고, 그렇게 걸린 시간을 출력해주면 끝난다.
여기서 유의할 점은
1. 얼음이 다 녹을 경우에 대한 조건 판단을 while의 초기에 넣어주어야 되는데, 이를 뒤에 넣게 되면 원래 얼음이 하나도 없을 경우에도 불필요한 탐색을 진행하게 되어 오답이 발생한다.
2. 너비우선탐색을 진행하기 전에 매번 방문 횟수를 저장해주는 visit_counts 를 초기화해주어야만 한다.
이 두가지만 잘 유의해준다면 오답이 발생하는 경우는 거의 없다고 보면 된다.
코드
import sys
from collections import deque
N, M = map(int, input().split())
env = []
for _ in range(N):
env.append(list(map(int, sys.stdin.readline().split())))
visit_counts = [[0 for _ in range(M)] for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for _ in range(N):
env.append(list(map(int, sys.stdin.readline().split())))
def bfs():
queue = deque()
init = [0,0]
queue.append(init)
visit_counts[0][0] = 1
# BFS을 통해 외부 공기에 접촉한 얼음에 대한 계산 진행
while queue:
x,y = queue.popleft()
for i in range(len(dx)):
# 위치 이동
new_x = x + dx[i]
new_y = y + dy[i]
if (0 <= new_x < M) and (0 <= new_y < N):
# 이동한 곳에 얼음이 있을 경우
if env[new_y][new_x] == 1:
# 방문 횟수를 1씩 누적
visit_counts[new_y][new_x] += 1
# 이동한 곳에 얼음이 없을 경우
elif (env[new_y][new_x]==0):
# 그 위치가 들리지 않은 곳일 경우에만 이동한다.
if (visit_counts[new_y][new_x] == 0):
# 방문 횟수를 1로 고정
visit_counts[new_y][new_x] = 1
# 얼음이 없는 쪽으로 이동한 곳은 결국 외부 공기와 접촉하는 다른 한 공간이 됨.
queue.append([new_x, new_y])
# 모든 방문 시뮬레이션을 마친 후 외부 공기에 의해 접촉한 횟수가 2 이상일 경우 얼음을 녹인다.
for y in range(N):
for x in range(M):
if visit_counts[y][x] >= 2:
env[y][x] = 0
time = 0 # 타이머
while True:
# 만약 얼음이 다 녹았을 경우 (그 경우 env는 0이 M개로 이루어진 리스트가 N개가 된다.)
# 이 부분은 무조건 앞에 두어야 한다. 그래야만 초기 값으로 모두 0이 주어진 경우에 불필요한 bfs를 진행하지 않게 됨.
if (env.count([0 for _ in range(M)]) == N):
break
visit_counts = [[0 for _ in range(M)] for _ in range(N)]
bfs()
time += 1
print(time)
