[BOJ] 2573. 빙산

Jimeaning·2023년 7월 11일

BFS 그래프

코딩테스트

목록 보기

111/143

Python3

문제

https://www.acmicpc.net/problem/2573

키워드

그래프 탐색
너비 우선 탐색
깊이 우선 탐색

문제 풀이

문제 요구사항

빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다.

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. (단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다.)

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

변수 및 함수 설명

n, m: 행의 개수와 열의 개수 (3 이상 300 이하)
adjMatrix: 빙산 정보 리스트. 각 칸에 들어가는 값은 0 이상 10 이하이다.
(배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.)

visited: 방문 처리 리스트
queue: bfs 사용하는 큐
dy, dx: 상하좌우
curY, curX: 현재 위치
ny, nx: 다음 이동할 위치

cnt: 빙산이 깎이는 양을 저장하는 리스트
result: 빙산이 두 덩어리가 될 때를 저장하는 리스트
day: 빙산이 쪼개질 때까지 며칠이 걸리는지 저장하는 변수

풀이

(입력 및 선언)

행과 열의 개수를 입력받고, 빙산의 정보를 저장한다.

(모든 얼음이 녹을 때까지 반복)

무한 반복문을 돌면서 모든 얼음이 녹을 때까지 반복한다.
반복문 안에 방문 처리 리스트와 얼음이 녹는 양 리스트를 초기화한다.

(빙산이 접촉한 바닷물을 확인하자)

adjMatrix를 돌며 빙산이 위치한 곳을 찾는다.
만약 adjMatrix 값이 0이 아니고 방문하지 않은 곳이라면, 큐에 해당 좌표를 넣고 방문 처리를 해준다.
bfs 함수를 실행한 값을 result 배열에 넣는다.

(bfs 함수)

큐에 원소가 없어질 때까지 반복한다.
큐의 첫 번째 원소를 curY, curX에 넣는다.
상하좌우 총 4번 반복한다.
다음 이동할 위치는 0보다 크거나 같고 n, m보다 작으며 방문하지 않은 곳이어야 한다.
만약 다음 이동할 위치의 빙산 높이가 0이 아니라면, 방문 처리를 하고 큐에 해당 좌표를 넣는다.
다음 이동할 위치의 빙산이 0이라면, cnt를 1 증가시켜 녹은 양을 기록한다.

(빙산을 깎자)

빙산이 접촉하고 있는 바닷물을 다 돈 후에 깎아야 주변 빙산에 영향을 주지 않는다.
n, m을 돌면서 반복문을 수행한다.
빙산이 물과 맞닿아 있었던 부분(cnt)을 빼준다.
이때 빙하가 0보다 작은 값이라면 0으로 바꿔준다.

(덩어리가 분리됐을 때를 찾자)

만약 result 길이가 0이면 두 덩어리로 분리되지 않았기 때문에 0을 출력하고 반복문을 종료한다.
만약 result 길이가 2가 되면 day값을 출력하고 반복문을 빠져 나온다.
아직 분리되지 않았다면, day 값을 1 증가시키고 더 깎는다.

최종 코드

from collections import deque

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

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

adjMatrix = []
queue = deque()

day = 0

def bfs():
    while queue:
        curY, curX = queue.popleft()
        for i in range(4):
            ny = curY + dy[i]
            nx = curX + dx[i]
            if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] == 0:
                if adjMatrix[ny][nx] != 0:
                    visited[ny][nx] = 1
                    queue.append((ny, nx))
                elif adjMatrix[ny][nx] == 0:
                    cnt[curY][curX] += 1

for _ in range(n):
    adjMatrix.append(list(map(int, input().split())))

while True:
    visited = [[0 for _ in range(m)] for _ in range(n)]
    cnt = [[0 for _ in range(m)] for _ in range(n)]
    result = []

    for i in range(n):
        for j in range(m):
            if adjMatrix[i][j] != 0 and visited[i][j] == 0:
                queue.append((i, j))
                visited[i][j] = 1
                result.append(bfs())

    for i in range(n):
        for j in range(m):
            adjMatrix[i][j] -= cnt[i][j]
            if adjMatrix[i][j] < 0:
                adjMatrix[i][j] = 0

    if len(result) == 0:
        print(0)
        break
    if len(result) >= 2:
        print(day)
        break

    day += 1