[소프티어 6281번] 동계 테스트 시점 예측

Softeer - 현대자동차그룹 SW인재확보플랫폼

import sys
from collections import deque

input = sys.stdin.readline

# 아침에 출근해보면 테스트 차량들 위에 눈얼음이 생겨있음
# 커다란 얼음이 녹고난 뒤에 테스트가 가능
# 차량마다 당일의 테스트 가능 시점을 알기 위한 예측 프로그램 제작

# N x M 크기의 격자 위에 눈 얼음의 모양을 작은 정사각형들이 집합되어 있는 모양으로 변환
# 아침이 되면 기온이 상승하여 천천히 녹는다

# 얼음은 상하좌우 중에서 적어도 2변 이상이 외부와 접촉했을 때 정확히 1시간만에 녹음
# 얼음 내부에 있는 공간은 얼음 외부 공기와 접촉하지 않는 걸로 가정

# 주어진 얼음이 모두 녹아서 사라지는데 걸리는 시간

n, m = map(int,input().split())

area = [list(map(int,input().split())) for _ in range(n)]

dx, dy = [-1,1,0,0], [0,0,-1,1]


time = 0

def check_all_malt():
    for i in range(n):
        for j in range(m):
            if area[i][j] == 1:
                return False
    return True

def bfs():

    visited = [[0]*m for _ in range(n)]

    queue = deque([(0,0)])
    visited[0][0] = True

    while queue:
        x, y = queue.popleft()

        visited[x][y] = -1

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:

                if area[nx][ny] == 1:
                    visited[nx][ny] += 1
                elif area[nx][ny] == 0 and visited[nx][ny] != -1:
                    visited[nx][ny] = -1
                    queue.append((nx,ny))
                    
    for i in range(n):
        for j in range(m):
            if visited[i][j] >= 2:
                area[i][j] = 0
                    
while True:
    if check_all_malt():
        break
        
    time += 1
    bfs()

print(time)

 

[백준 2636번] 치즈

 

이번 문제는 이전에 풀이했던 백준 2636번 치즈 문제와 동일한 문제이다.

 

특정 영역(얼음)들을 기준으로 바깥 쪽에 있는 공간을 공기, 안 쪽에 있는 부분을 공기가 차단된 공간이라고 하고 공기와 2개 이상 맞닿아있는 영역이 1시간에 한번씩 녹는다는 가정하에 모든 영역이 녹는데 걸리는 시간을 구하는 문제이다.

 

1. 먼저 공기와 맞닿아있는 영역을 체크하기 위해 바깥쪽 공간에서 BFS 알고리즘을 실행하여 모든 공기 좌표를 방문(방문처리는 visited 2차원 배열에 -1 을 저장)
2. 방문하는 과정에서 상하좌우에 얼음이 존재하면 visited 2차원 배열에 카운팅 + 1
3. 맞닿아있는 공기가 2개 이상인 경우 해당 영역의 얼음을 녹임(area[i][j] = 0)

위 과정을 통해 얼음을 1시간마다 녹여주었고, 모든 얼음이 녹았는지 확인하는 함수(check_all_malt)를 통해 총 걸리는 시간을 카운팅해주었다.