[JavaScript] 백준 2636 치즈 (JS)

치즈

📚 문제 설명

N * M 의 사각형 판의 테두리를 제외한 부분에 치즈가 놓여있다.
치즈는 공기와 만나면 1시간 후에 녹아서 사라진다고 할 때
치즈가 완전히 사라지는데 걸리는 시간과, 완전히 사라지기 전 마지막 치즈의 크기를 구하여라.

단, 치즈에 구멍이 있을 수 있지만 해당 구멍에는 공기가 없다고 한다.

예를 들면 아래와 같다.

1이 치즈이고 0이 공기라고 한다.

0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0

공기와 마주하면 치즈가 2로 변한다고 하면

0 0 0 0 0
0 2 2 2 0
0 2 1 2 0
0 2 2 2 0
0 0 0 0 0

1시간 후는 아래와 같이 바뀐다.

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

2시간 후

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

따라서 정답은 아래와 같다.
2
1

👨🏻‍💻 풀이 과정

문제를 읽고 BFS를 사용하여 치즈를 없애야 한다는 사실은 알았지만, 2가지 생각이 들었다.
1. 치즈를 기준으로 BFS를 진행하여 공기와 닿은 것을 없애는 방법.
2. 공기를 기준으로 BFS를 진행하여 인접한 치즈를 없애는 방법.

1번 방법의 경우 Map 배열을 전체를 확인하며 치즈를 찾아서 BFS 함수에 넣어야하는 점과 공기와 닿지 않은 치즈의 구멍을 구분하기 어렵다는 문제가 있었다.

2번 방법의 경우 Map 배열을 탐색하여 공기를 찾을 필요 없이 Map[0][0] 은 무조건 공기이고 치즈 구멍 또한 구분할 수 있다.

따라서 2번 방법을 이용하여 로직을 구현했다.

전체 로직

• 치즈 총 갯수 계산하여 CheeseExist에 저장.
• 치즈가 없어질 때까지 BFS 실행.
  • 0,0 부터 다음위치(상하좌우) 확인.
  • 다음 위치가 0이라면 Queue에 다음 위치 삽입.
  • 다음 위치가 1이라면
    • Rotten 증가.
    • 다음 위치 값 0으로 변경.
  • Rotten 값 리턴.
• CheeseExist에서 Rotten을 빼준다. (남은 치즈 갯수가 나온다.)
• timer 증가.
• 결과 리턴.

전체 코드

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let [N, M] = input.shift().split(' ').map(Number);
    let Map = input.map(v => v.split(' ').map(Number));
	// BFS 함수.
    const BFS = (x, y) => {
      	// 이미 방문한 값 기록.
        let visited = Array.from({length: N}, _ => Array(M).fill(false));
      	// 큐에 현재 위치 넣기.
        let Queue = [[x, y]];
      	// 현재 위치 visited 배열에 갱신.
        visited[x][y] = true;
      	// shift() 를 쓰지 않기 위해 인덱스 값 이용.
        let idx = 0;
      	// 상하좌우 이동 변수.
        let dx = [1, -1, 0, 0];
        let dy = [0, 0, 1, -1];
      	// 녹아서 사라질 치즈 갯수.
        let Rotten = 0;
        while (Queue.length > idx) {
            let [X, Y] = Queue[idx];
            for (let i = 0; i < dx.length; i++) {
                const NextX = X + dx[i];
                const NextY = Y + dy[i];
              	// Map 바깥으로 나갈 경우.
                if (NextX < 0 || NextX >= N || NextY < 0 || NextY >= M) continue;
              	// 아직 가지 않은 곳이라면.
                if (!visited[NextX][NextY]) {
                  	// 다음 위치가 공기라면.
                    if (Map[NextX][NextY] === 0) {
                        visited[NextX][NextY] = true;
                        Queue.push([NextX, NextY]);
                     // 다음 위치가 치즈라면.
                    }else if (Map[NextX][NextY] === 1) {
                        visited[NextX][NextY] = true;
                        Map[NextX][NextY] = 0;
                        Rotten++;
                    }
                }

            }
            idx++;
        }
      	// 녹은 치즈 갯수 리턴.
        return Rotten;
    };

    const solution = () => {
        let timer = 0;
      	// 남은 치즈 갯수
        let CheeseExist = 0;
      	// 녹은 치즈.
        let RottenCheese = 0;
      	// 전체 치즈 갯수 
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (Map[i][j] === 1) {
                    CheeseExist++;
                }
            }
        }
        while (CheeseExist > 0) {
          	// 녹은 치즈
            RottenCheese = BFS(0, 0);
          	// 남은 치즈 갱신.
            CheeseExist = CheeseExist - RottenCheese;
            timer++;
        }
        console.log(`${timer}\n${RottenCheese}`);
    };
    solution();

🧐 후기

문제 로직 구현은 쉬웠지만 첫번째 제출에서 타입에러가 나게 되었다.
타입 에러가 나는 것을 확인하고 혹시라도 배열 범위가 잘못되었나 확인하고 정답 출력이 잘못되었는지, 반례가 있는지 모두 확인하고 나서야 입력이 잘못되었다는 것을 발견했다.

로컬 환경에서 구현을 하고 백준 제출을 위해 복사하는 과정에서 이상한 코드가 입력 부분에 함께 복사된 것이 문제였다.