동계 테스트 시점 예측

태그

BFS

링크

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=411&sw_prbl_sbms_sn=57105

체크 필요

* 백준 2638번: 치즈 문제와 동일하다.

문제

북위 65도. 스웨덴의 소도시 아르예플로그(Arjeplog)에 자리한 동계 테스트 센터.

겨울 내내 얼음 두께가 1M 내외로 유지되는 광할한 얼음 호수와 그냥 걷기조차 힘든 눈길을 무대로 현대자동차그룹 연구원들은 극한 환경 속에서 더 나은 차량 성능을 확보하기 위해 제동안정성, 주행안정성, ADAS 기능 등에 대한 다양한 평가를 숨가쁘게 이어가고 있다.

이 곳은 기온이 너무 추워서 아침에 출근해보면 테스트 차량들 위에 큰 눈얼음이 생겨 있다. 정상적인 테스트를 위해서는 커다란 얼음이 어느정도 녹고 난 뒤에 가능한데, 차량 마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램을 제작 중에 있다.

[그림1]

예측 프로그램은 N×M (5 ≤ N, M ≤ 100)의 격자 화면 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환하여 [그림 1]과 같이 표시해 준다.

단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 얼음은 아침이 되면 기온이 상승하여 천천히 녹는다.

그런데 화면에서 나타난 얼음의 모양은 작은 정사각형 모양의 4변 중에서 적어도 2변 이상이 외부의 공기와 접촉했을 때 정확히 한 시간 만에 녹아 없어져 버린다.

따라서 아래 [그림 1] 모양과 같은 얼음(파란으로 표시된 부분)라면 C로 표시된 모든 얼음 격자는 한 시간 후에 사라진다.

[그림2]

[그림 2]와 같이 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 얼음 격자는 녹지 않고 C로 표시된 얼음 격자만 사라진다.

그러나 한 시간 후, 이 공간으로 외부공기가 유입되면, 아래 [그림 3]에서와 같이 C로 표시된 얼음 격자들이 사라지게 된다.

[그림3]

격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 것으로 가정한다. 입력으로 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성해보자.

입력

첫째 줄에는 격자 화면의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다.

그 다음 N개의 줄에는 격자 화면 위에 얼음이 있는 부분은 1로 표시되고, 얼음이 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 얼음이 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

예시

입력

Plain Text
복사

출력

Plain Text
복사

정답

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

snow_matrix = []

# 격자 만들기
for i in range(N):
    snow_matrix.append(list(map(int, sys.stdin.readline().split())))

# 외부 공기 -1로 변환
def outside(matrix):
    visited = [[False]*M for _ in range(N)]   # 방문 여부
    
    dq = deque()     # 방문해야 하는 위치
    dq.append([0,0])

    dy = [-1,1,0,0]  # 상하
    dx = [0,0,-1,1]  # 좌우
    matrix[0][0] = -1    # 맨 가장자리는 무조건 외부 공기
    visited[0][0] = True  # 방문 처리

    # 방문해야 하는 곳이 남지 않을 때까지 반복
    while dq:
        y, x = dq.popleft()   # 방문 위치 pop
        for i in range(4):    # 상하좌우 확인
            new_y = y + dy[i]
            new_x = x + dx[i]
            if (new_y < 0) or (new_y > (N-1)) or (new_x < 0) or (new_x > (M-1)): continue   # 인덱스가 맞지 않는 경우 pass
            if (matrix[new_y][new_x] == 1) or (visited[new_y][new_x]==True): continue    # 이미 방문했거나 얼음이 있는 곳인 경우 pass
            
						# new_y, new_x는 외부 공기랑 맞닿아 있으면서 얼음이 아닌 상황 -> 마찬가지로 외부 공기임
						matrix[new_y][new_x] = -1    # 외부 공기 변환
            visited[new_y][new_x] = True  # 방문 처리
            dq.append([new_y, new_x])    # 현재 위치에서 사방탐색 진행
    return

# 얼음이 하나도 안 남았는지 확인
def is_melt(matrix):
    N = len(matrix)
    M = len(matrix[0])
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                return False
    return True

# 시간 계산 function
def time_predict(matrix, N, M):
    answer = 0
    dy = [-1,1,0,0]  # 상하
    dx = [0,0,-1,1]  # 좌우
    
    # 얼음이 남아있지 않을 때까지 반복
    while is_melt(matrix) == False:
        outside(matrix)   # 외부 공기 초기화
        deleted = []      # 녹일 리스트
	      
	      # 가장 자리를 제외한 내부 공간 탐색
        for i in range(1, N-1):
            for j in range(1, M-1):
                cnt = 0    # 맞닿아 있는 외부 공기의 개수
                for s in range(4): 
                    new_i = i + dy[s]
                    new_j = j + dx[s]
                    if matrix[new_i][new_j]==-1:
                        cnt += 1
                if cnt >=2 :   # 맞닿아 있는 외부 공기의 개수가 2이상
                    deleted.append([i,j])   # 녹일 리스트에 저장
        for y, x in deleted:  # 녹일 리스트에 있는 얼음들 녹이기
            matrix[y][x] = -1
        answer += 1    # 시간 경과
    return answer

print(time_predict(snow_matrix, N, M))
Python
복사

풀이

•

BFS로 풀어야 하는 문제이다.

•

우선 step은 간단하다.

녹일 얼음이 있는지 확인

조건에 맞는 얼음 녹이기

시간 경과 +1 해주기

•

다만 포인트는 외부 공기와 내부 공기를 구분해주는 것이다. 얼음은 외부 공기에만 영향을 받기 때문이다.

•

이때 외부 공기인지 아닌지를 파악하기 위해서 BFS를 사용한다.

•

사방탐색(상하좌우 탐색)을 진행해서 만약 상하좌우에 하나라도 외부 공기가 있다면 현재 탐색하고 있는 위치 역시 외부 공기임을 이용한다.

◦

내부 공기는 외부 공기와 만날 수 없으며

◦

문제에서 맨 가장자리는 항상 외부 공기이기 때문에 가능하다.

•

따라서 우선 외부 공기를 0이 아니라 -1로 변환해주는 function을 만든다.

•

우선 외부 공기임을 확인했던 곳을 또 확인해서는 안 되기 때문에 (아니면 무한 반복에 빠짐) 격자별 방문 여부 matrix를 만든다.

•

사실 엄밀하게 얘기하면 visited는 방문을 이미 한 곳이라기 보다는 deque에 이미 포함을 시켰던 위치로 보는 것이 맞다. 이는 뒤에서 조금 더 자세히 설명한다.

visited = [[False]*M for _ in range(N)]   # 방문 여부
Python
복사

•

그 다음 방문해야 하는 위치를 담고 있는 덱(deque)을 만든다.

•

가장 먼저 방문해야 하는 위치는 외부 공기임이 확실한 [0,0] 이다.

•

그리고 [0,0] 위치는 외부 공기이므로 -1 변환을 해주고 방문 처리도 해준다.

dq = deque()     # 방문해야 하는 위치
dq.append([0,0])
matrix[0][0] = -1    # 맨 가장자리는 무조건 외부 공기
visited[0][0] = True  # 방문 처리
Python
복사

•

이제 [0,0] 부터 시작해서 방문해야 하는 위치가 남지 않을 때까지 반복해서 변환을 시행한다.

•

우선 방문해야 하는 덱에서 popleft()를 사용해서 방문 위치를 뽑아내고 사방탐색을 진행한다.

•

만약 새로운 y와 x의 좌표인 new_y와 new_x가 인덱스 허용 범위를 넘는다면 고려할 필요가 없으므로 continue로 패스해준다.

 for i in range(4):    # 상하좌우 확인
	new_y = y + dy[i]
	new_x = x + dx[i]
	if (new_y < 0) or (new_y > (N-1)) or (new_x < 0) or (new_x > (M-1)): continue   # 인덱스가 맞지 않는 경우 pass
Python
복사

•

그리고 만약 new_y, new_x 위치에 얼음이 존재하거나 이미 방문했던 곳(이미 덱에 포함되었던 위치)이라면 변환할 필요가 없으므로 마찬가지로 continue로 패스한다.

if (matrix[new_y][new_x] == 1) or (visited[new_y][new_x]==True): continue    # 이미 방문했거나 얼음이 있는 곳인 경우 pass
Python
복사

•

이제 남은 경우는 외부 공기랑 맞닿아 있으면서 얼음도 아니고 인덱스도 맞으며 아직 덱에 포함되지 않았던 위치이다. 따라서 이 위치를 사방 탐색을 진행할 덱에 포함시키고 외부 공기로 변환해준다. 그리고 방문 처리도 해준다.

→ 아직 탐색을 하지 않았음에도 방문처리를 하는 이유는 미리 방문처리를 해놓아야 다른 위치에서 사방탐색을 진행할 때 중복해서 포함이 되지 않기 때문이다. 예를 들어 다음과 같은 격자에서 미리 방문처리를 안 한다고 가정해보자.

a b c

d e f

g h i

d와 f가 외부 공기이고 e가 얼음이 아니라고 하자. 그러면 d를 탐색할 때 e는 외부 공기이므로 덱에 포함된다. 그리고 e보다 f가 먼저 덱에 포함이 되어서 f를 먼저 탐색한다고 하자. 그러면 f를 탐색할 때 e는 외부 공기이므로 또 덱에 포함되게 된다. 즉, e는 이미 덱에 있음에도 중복해서 포함되게 되는 것이다. 따라서 이를 방지하기 위해 먼저 방문 처리를 해야 한다.

matrix[new_y][new_x] = -1    # 외부 공기 변환
visited[new_y][new_x] = True  # 방문 처리
dq.append([new_y, new_x])    # 현재 위치에서 사방탐색 진행
Python
복사

•

우리는 앞에서 step1 (녹일 얼음이 있는지 확인)을 진행해줄 function도 필요하다. 이것은 그냥 격자 하나씩 살펴보면서 1이 존재하면 False를 뱉도록 만들면 된다.

# 얼음이 하나도 안 남았는지 확인
def is_melt(matrix):
    N = len(matrix)
    M = len(matrix[0])
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                return False
    return True
Python
복사

•

이제 is_melt와 outside를 활용하여 시간 측정 function을 만든다.

•

우선 얼음이 하나도 안 남았는지를 체크해서 True가 나올 때까지 얼음 녹이기를 반복한다.

# 얼음이 남아있지 않을 때까지 반복
while is_melt(matrix) == False:
Python
복사

•

가장 먼저 외부 공기 격자를 초기화한다. → 왜냐하면 이전 단계에서 얼음을 녹이면 외부 공기가 변하기 때문

outside(matrix)   # 외부 공기 초기화
Python
복사

•

그 다음 얼음을 녹일 격자의 위치를 담을 리스트를 만든다. 그 이유는 얼음은 녹일 위치를 전부 확인하고 나서 한 번에 녹여야 하기 때문이다. → 안 그러면 중간에 얼음이 -1로 바뀌어서 다른 얼음을 체크할 때 영향을 주기 때문.

deleted = []      # 녹일 리스트
Python
복사

•

이제 가장자리를 제외한 내부 공간 [1,1] 부터 [N-2, M-2]까지를 하나씩 탐색한다.

•

그리고 얼음인 경우 사방탐색을 진행해서 -1이 두 개 이상 포함된 경우 녹일 리스트에 추가한다.

•

내부 공간 탐색을 마치면 녹일 리스트에 있는 격자의 값을 -1로 변환한다. (얼음 → 외부 공기)

•

변환을 마치면 시간이 경과하므로 시간에 +1을 해준다.

# 가장 자리를 제외한 내부 공간 탐색
for i in range(1, N-1):
	for j in range(1, M-1):
		cnt = 0    # 맞닿아 있는 외부 공기의 개수
		for s in range(4): 
			new_i = i + dy[s]
			new_j = j + dx[s]
			if matrix[new_i][new_j]==-1:
				cnt += 1
      if cnt >=2 :   # 맞닿아 있는 외부 공기의 개수가 2이상
				deleted.append([i,j])   # 녹일 리스트에 저장
for y, x in deleted:  # 녹일 리스트에 있는 얼음들 녹이기
	matrix[y][x] = -1
answer += 1    # 시간 경과
Python
복사