[백준/1996번] 지뢰 찾기 (node.js)

문제

문제

입출력

 

다들 문제보자마자 대충 이렇게 풀어야겠다 머릿속에 떠오르죠?

 

실버5의 구현 문제기도 해서 큰 난이도를 자랑하는 문제는 아니지만 

"다른 사람은 어떻게 풀었지?" 라고 생각하는 사람도 생길거라 생각해 남겨봅니다

 

이 문제는 크게 두 가지 방법으로 풀 수 있는데요 

---

풀이

풀이 1 - 지뢰를 기준으로 인접한 칸들의 지뢰 개수를 더한다

풀이1- 지뢰기준

간단하게 설명하자면

1. 처음 칸부터 시작하다 지뢰(정수)를 만나면
2. 새로운 배열에서 지뢰가 있던 자리를 표시하고 
3. 주변 칸에 지뢰 수만큼 더해준다
4. 그리고 10넘는 지뢰들은 "M" 으로 만들어준다 

 

지뢰를 기준으로 주변의 가중치를 더해주는 방법입니다

// 입력부분
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);
const grid = input.slice(1).map(row => row.split(""));
const result = Array.from({ length: N }, () => Array(N).fill(0));

const directions = [
  [-1, -1], [-1, 0], [-1, 1],
  [0, -1],          [0, 1],
  [1, -1], [1, 0],  [1, 1],
];

// 지뢰 기준으로 주변 8칸에 숫자 더하기
for (let x = 0; x < N; x++) {
  for (let y = 0; y < N; y++) {
    if (grid[x][y] !== ".") {
      const value = Number(grid[x][y]);
      result[x][y] = "*";

      for (const [dx, dy] of directions) {
        const nx = x + dx;
        const ny = y + dy;

        if (
          nx >= 0 && nx < N &&
          ny >= 0 && ny < N &&
          result[nx][ny] !== "*"
        ) {
          result[nx][ny] += value;
        }
      }
    }
  }
}

// 숫자 후처리
for (let x = 0; x < N; x++) {
  for (let y = 0; y < N; y++) {
    if (result[x][y] !== "*" && result[x][y] >= 10) {
      result[x][y] = "M";
    } else if (result[x][y] !== "*") {
      result[x][y] = result[x][y].toString();
    }
  }
}

console.log(result.map(row => row.join("")).join("\n"));

 

풀이 2 - 칸을 기준으로 인접한 지뢰들의 개수를 더한다

풀이2 - 공백기준

이렇게 공백을 기준으로 풀 수도 있는데요 

1. 일단 "." 들을 전부 숫자 0, 지뢰들의 숫자들의 타입을 정수로 바꿔준다
2. 처음 칸부터 시작하다 공백을 만나면 주변에 모든 지뢰를 더한다
3. 그리고 10넘는 지뢰들은 "M" 으로 만들어준다

 

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);
const grid = input.slice(1).map(row =>
  row.split("").map(c => (c === "." ? 0 : Number(c)))
);
const result = Array.from({ length: N }, () => Array(N).fill(0));

const directions = [
  [-1, -1], [-1, 0], [-1, 1],
  [0, -1],          [0, 1],
  [1, -1], [1, 0],  [1, 1],
];

for (let x = 0; x < N; x++) {
  for (let y = 0; y < N; y++) {
    if (grid[x][y] > 0) {
      result[x][y] = "*";
      continue;
    }

    let sum = 0;
    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      if (nx >= 0 && nx < N && ny >= 0 && ny < N && grid[nx][ny] > 0) {
        sum += grid[nx][ny];
      }
    }

    result[x][y] = sum >= 10 ? "M" : sum.toString();
  }
}

console.log(result.map(row => row.join("")).join("\n"));​

---

비교 

그래서 방법1, 방법2 중에 어떤 방법을 써야할까?

 

지뢰의 총 개수를 G 라고 할 때

 

방법 1의 연산 횟수는 G*8 입니다. 지뢰의 개수에 따라 연산 횟수가 달라집니다

방법 2의 연산 횟수는 (N × N) * 8입니다. 지뢰가 몇 개 있던 모든 칸을 다 검사하지만 연산 횟수는 고정적입니다

 

- 지뢰의 갯수가 많다면? (100 x 100 판의 20개의 지뢰 )

지뢰 기준	20 * 8 = 160 회 연산	적음
빈칸 기준	10000 * 8 = 80000 회 연산	많음

 

- 하지만 지뢰가 50%를 넘어간다면 ?

지뢰가 매우 적음	G * 8 → 매우 작음	✅ 지뢰 기준 퍼뜨리기
지뢰가 거의 없음	(N*N) * 8 → 비효율	❌ 빈칸 기준 불리함
지뢰가 많음 (50% 이상)	지뢰 기준은 중복 많음	✅ 빈칸 기준이 오히려 빠름

 

이처럼 G 가 N * N 보다 커지는데 주의하면 어떤 방식이 유용한지 알 수 있습니다

결론 

사실 연산 횟수가 크게 중요하지 않은 문제기도 하지만 (시간복잡도도 같음)

어느 한 가지 방법을 선택했을 때 왜 이 방식으로 풀었나 물어보면 어떻게 대답할지 막막해서 정리해봤습니다 

• 지뢰가 적다 → 방법 1 (지뢰 기준)
• 전체 결과가 필요하다 → 방법 2 (탐색 방식)