[백준] 2636. 치즈 풀이 (Python, TypeScript)

2636번: 치즈

접근한 방법

7576. 토마토 문제와 살짝 비슷합니다. 내부, 외부 공간을 굳이 구분할 필요는 없고 매 시간마다 처음 (0, 0) 좌표에서만 bfs를 수행하면서 치즈를 만나는 경우만 체크하여 제거 리스트에 올려주고 그 외 공간은 모두 탐색을 계속 진행하면 됩니다. 치즈를 만나는 경우는 탐색 대상에 들어가지 않기 때문에 애초에 치즈로 둘러쌓인 공간을 탐색할 일이 없습니다.

 

1. 전체 치즈 수를 체크합니다.

2. 좌표 0, 0 에서 bfs를 실행합니다. 상하좌우를 확인하여 공기만 경우 큐에 넣고 그 외엔 전부 제거리스트(target)에 넣습니다.

3. 제거리스트를 순회하여 모두 공기로 바꿔줍니다.

4. 전체 치즈 수에서 제거리스트에 들어간 개수를 제외해줍니다.

5. 2~4를 반복하며 전체 치즈 수가 0이 되면 반복 횟수와 마지막으로 체크한 제거리스트의 개수를 리턴합니다.

 

Python

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(list(map(int, input().split())) for _ in range(n))
result, time = 0, 0
for i in arr:
    result += i.count(1)
import collections
dist = ((-1, 0), (1, 0), (0, -1), (0, 1))
def bfs():
    visited = [[0] * m for _ in range(n)]
    q = collections.deque()
    q.append((0, 0))
    target = []
    while q:
        qr, qc = q.popleft()
        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 visited[dr][dc]:
                continue
            visited[dr][dc] = 1
            if not arr[dr][dc]:
                q.append((dr, dc))
            else:
                target.append((dr, dc))
    for t in target:
        arr[t[0]][t[1]] = 0
    return len(target)

while 1:
    time += 1
    cnt = bfs()
    result -= cnt
    if not result:
        print(time), print(cnt)
        break

TypeScript

function sol2636(n: number, m: number, arr: Array<Array<number>>) {
  let [result, time] = [0, 0];
  for (const a of arr) {
    result += a.reduce((accr, curr) => accr + curr, 0);
  }
  const dist = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  const bfs = () => {
    const visited = Array.from({ length: n }, () => Array(m).fill(0));
    const q = [[0, 0]];
    let front = 0;
    const target = [];
    while (q[front]) {
      const [qr, qc] = q[front++];
      for (const d of dist) {
        const [dr, dc] = [qr + d[0], qc + d[1]];
        if (dr < 0 || dc < 0 || dr >= n || dc >= m || visited[dr][dc]) continue;
        visited[dr][dc] = 1;
        if (!arr[dr][dc]) q.push([dr, dc]);
        else target.push([dr, dc]);
      }
    }
    target.forEach((t) => {
      arr[t[0]][t[1]] = 0;
    });
    return target.length;
  };
  while (1) {
    time += 1;
    const cnt = bfs();
    result -= cnt;
    if (!result) return [time, cnt];
  }
}