[백준] 2573. 빙산 풀이 (Python, TypeScript)

2573번: 빙산

접근한 방식

1. 입력으로 n, m을 받고, 2차원 배열 arr에 빙산 정보를 저장합니다. 

2. 주어진 4방향(dist)을 이용하여 빙산이 한 덩어리로 얼마나 오래 지속되는지 계산하는 solution 함수를 정의합니다. 

3. dfs를 정의하고 모든 빙산이 연결되어 있는지 확인합니다. 

4. solution 함수에서는 빙산이 1개로 이루어져 있거나 빙산이 나뉘어 있는 경우까지 계속 반복하여 빙산을 녹이고, 빙산이 1개로 이루어져 있을 때까지 걸리는 시간을 반환합니다.

 

주의할 점은 빙산이 1개만 남거나 다음 회차에 빙산이 다 녹아버리는 경우는 0을 반환해주어야 합니다.

 

 

Python (Pypy3)

import sys
sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
import collections
def solution():
    def dfs(r, c, vst):
        if vst[r][c]:
            return 0
        vst[r][c] = 1
        for d in dist:
            dr, dc = r + d[0], c + d[1]
            if dr < 0 or dc < 0 or dr >= n or dc >= m:
                continue
            if not vst[dr][dc]:
                dfs(dr, dc, vst)
        return 1
    dist = ((-1, 0), (1, 0), (0, -1), (0, 1))
    result = 0
    while 1:
        q = collections.deque()
        vst = [[1] * m for _ in range(n)]
        for i in range(n): # 녹지않은 빙산 체크
            for j in range(m):
                if arr[i][j]:
                    vst[i][j] = 0
                    q.append((i, j))
        if len(q) == 1: # 빙산이 1개남은 경우
            return 0
        f = 0 # 종료 플래그
        for i in range(n):
            for j in range(m):
                f += dfs(i, j, vst)
                if f == 2: # 빙산이 나뉘어 있는 경우
                    return result
        cand = [] # 녹아야할 빙산 리스트
        while q:
            qr, qc = q.popleft()
            cnt = 0
            for d in dist:
                dr, dc = qr + d[0], qc + d[1]
                if dr < 0 or dc < 0 or dr >= n or dc >= m:
                    continue
                if not arr[dr][dc]: # 주변 물의 칸 수 체크
                    cnt += 1
            if cnt:
                cand.append((qr, qc, cnt))
        for (r, c, v) in cand: # 빙산 녹이기
            if arr[r][c] - v < 0:
                arr[r][c] = 0
            else:
                arr[r][c] -= v
        result += 1
        if not cand: # 빙산이 다 녹은 경우
            return 0
print(solution())

TypeScript

function sol2573(n: number, m: number, arr: Array<Array<number>>) {
  const dfs = (r: number, c: number, vst: Array<Array<number>>) => {
    if (vst[r][c]) return 0;
    vst[r][c] = 1;
    for (const d of dist) {
      const [dr, dc] = [r + d[0], c + d[1]];
      if (dr < 0 || dc < 0 || dr >= n || dc >= m) continue;
      if (!vst[dr][dc]) dfs(dr, dc, vst);
    }
    return 1;
  };
  const dist = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  let result = 0;
  while (1) {
    const q = [];
    const vst = Array.from({ length: n }, () => Array(m).fill(1));
    let front = 0;

    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < m; j += 1) {
        if (arr[i][j]) {
          vst[i][j] = 0;
          q.push([i, j]);
        }
      }
    }
    if (!q[front + 1]) return 0;
    let f = 0;
    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < m; j += 1) {
        f += dfs(i, j, vst);
        if (f == 2) return result;
      }
    }
    const cand = [];
    while (q[front]) {
      const [qr, qc] = q[front++];
      let cnt = 0;
      for (const d of dist) {
        const [dr, dc] = [qr + d[0], qc + d[1]];
        if (dr < 0 || dc < 0 || dr >= n || dc >= m) continue;
        if (!arr[dr][dc]) cnt += 1;
      }
      if (cnt) cand.push([qr, qc, cnt]);
    }
    cand.forEach((cd) => {
      const [r, c, v] = cd;
      if (arr[r][c] - v < 0) arr[r][c] = 0;
      else arr[r][c] -= v;
    });
    result += 1;
    if (!cand[0]) return 0;
  }
}

console.log(
  sol2573(5, 7, [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 3, 6, 0, 6, 7, 0],
    [0, 3, 0, 0, 0, 10, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
  ])
);