[백준 알고리즘] Node.js 1996. 지뢰 찾기

1. 문제

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

1996번: 지뢰 찾기

 

2. 풀이

• 8방향 탐색을 진행하기 위해 사전에 array로 움직일 위치들을 만들어주었다.
• 이중 반복을 통해 각 위치를 탐색했고, 탐색을 통해 '.' 아니라면 '*' 로, 그 이외엔 주변 탐색을 진행했다.

const inputs = require('fs').readFileSync('/dev/stdin') 
              .toString().trim().split('\n');
const N = +inputs.shift();
const mine = Array.from({length : N}, () => new Array(N).fill(0));

// 해당 좌표가 표 안에 존재하는지, . 이 아닌지 확인하는 함수.
const isInArray = (y, x) => {
  if(y >= 0 && y < N && x >= 0 && x < N && inputs[y][x] !== '.') return true;

  return false;
}

// 8방향 검색을 위한 변수 설정.
const dx = [-1, -1, -1, 0, 0, 1, 1, 1];
const dy = [-1, 0, 1, -1, 1, -1, 0, 1]

for(let i = 0; i < N; i++){
  for(let j = 0; j < N; j++){
    if(inputs[i][j] !== '.'){ // . 아니라면 숫자이기에 숫자는 * 로 표시.
      mine[i][j] = '*';
    } else {
      let cnt = 0;
      for(let k = 0; k < 8; k++){ // 8방향 검색
        let nx = i + dx[k];
        let ny = j + dy[k];

        if(isInArray(nx, ny)){ // 해당 좌표가 표 안에 있고 .이 아니라면 값을 더해줌.
          cnt += +inputs[nx][ny]
        }
      }
      if(cnt >= 10) mine[i][j] = 'M'; // 10이상이면 M 으로 변경.
      else mine[i][j] = cnt.toString(); // 10보다 작다면 숫자를 string 형태로 변경.
    }
  }
}

let result = "";
mine.forEach(line => {
  line.forEach(item => {
    result += item;
  })

  result += '\n';
})

console.log(result);

 

3. 정리

• 처음엔 접근을 숫자가 있는 곳을 기준으로 잡았다. 숫자가 존재하는 곳을 기준으로 8방향에 값을 더하는 방식을 채택했었다. 아래는 해당 코드다. 이 코드는 정답이 아니다.

const inputs = require('fs').readFileSync('/dev/stdin') 
              .toString().trim().split('\n');
const N = +inputs.shift();
const mine = Array.from({length : N}, () => new Array(N).fill(0));

const isInArray = (y, x) => {
  if(y >= 0 && y < N && x >= 0 && x < N) return true;
  return false;
}

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

for(let i = 0; i < N; i++){
  for(let j = 0; j < N; j++){
    if(inputs[i][j] !== '.'){
      mine[i][j] = '*';

      for(let k = 0; k < 8; k++){
        let nx = i + dx[k];
        let ny = j + dy[k];

        if(isInArray(nx, ny)){
          mine[nx][ny] += parseInt(inputs[i][j]);
          if(mine[nx][ny] >= 10) mine[nx][ny] = 'M';
        }
      }
    }
  }
}

let result = "";
mine.forEach(line => {
  line.forEach(item => {
    result += item;
  })
  result += '\n';
})

console.log(result);

• 정답코드와 다른 점은 어느 점을 기준으로 잡았느냐의 차이였다. 나는 숫자가 표현되어있는 걸 기준으로 잡았고, 정답코드는 ' . ' 을 기준으로 잡았다.
  • 위의 코드는 숫자를 기준으로 잡아 8방향에 숫자를 더해주는 방식.
  • 정답코드는 ' . ' 을 기준으로 잡아 8방향에 숫자가 있다면, 그 숫자를 가져와서 더하는 방식.
• 비슷한 방식이라고 생각해서 계속 수정해봤는데, 반례가 없어서 어디서 문제가 생겼는지 알 수 없어서 많이 답답하다. 심지어 다른 분들도 정답과 비슷하게 작성하셨고, 푼 사람도 적다..............
• 혹시 이 글을 보시는 분들이 계시면 어떤 점이 다른지 댓글 달아주셨으면 좋겠다.........