문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

38

예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

13

나의 코드

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n")
  .map((row) => row.split(""));
const [N, M] = [
  Number(input[0].join("").split(" ")[0]),
  Number(input[0].join("").split(" ")[1]),
];
input.shift();
console.log(solution(0, 0));

function solution(x, y) {
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];
  let marking = [...Array(N)].map((_) => [...Array(M)].map((v) => (v = 1)));
  let queue = [];
  queue.push([x, y]);

  function bfs(x, y) {
    while (true) {
      [x, y] = queue.shift();

      if (marking[N - 1][M - 1] > 1) return marking[N - 1][M - 1];
      for (let i = 0; i < 4; i++) {
        let nx = x + dx[i];
        let ny = y + dy[i];

        if (input[nx]?.[ny] === "0") continue;
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (marking[nx][ny] > 1) continue;
        marking[nx][ny] = marking[x][y] + 1;
        queue.push([nx, ny]);
      }
    }
  }
  return bfs(0, 0);
}

지금까지는 bfs를 풀면서 기존 코드를 꽤 많이 참고했지만, 이번에는 기존 코드 참고 없이 풀어봤다. 참고 자료 없이도 이제 전형적인 bfs는 구현할 수 있게 되었다. 여느 때와 같이 전형적인 bfs 코드였지만, 중간에 실수해서 시간을 잡아먹은 부분들을 짚고 넘어가려고 한다.

어이없게도 입력 받는 부분에서 절어버려서 시간을 많이 뺏겼다.

처음에 N과 M을 입력받을 때

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n")
  .map((row) => row.split(""));
  
 const [N, M] = [input[0], input[2]];

이렇게 입력했다가 M이 2자리 수가 되었을 때 결과가 엉뚱하게 나왔다.
M이 한자리 수인 경우만 고려했다가 낭패를 본 것이다!!

다급하게 리팩토링하다가 아래 코드까지 꼬여버려서 일단

const [N, M] = [
  Number(input[0].join("").split(" ")[0]),
  Number(input[0].join("").split(" ")[1]),
];

이렇게 다소 지저분하게 입력을 받아버렸다. ㅋㅋㅋㅋ

이 부분을 다시 입력받을 수 있다면

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n");
  
const [N, M] = input[0].split(" ").map(Number);
input.shift();

이렇게 받아올 것이다.

앞으로 주의하도록 쨰스민!

요즘 DP를 풀고 있는데 조금만 깊게 들어가려고 해도 어렵다..
2 x N 타일링 2(외 다수의 문제)에서 막혔다...띠로롱...타일은 제발 한 종류만 써주면 안 되겠니..
잠시 BFS를 풀어봤는데 역시 구관이 명관인건지 저번주에 일주일동안 bfs를 파서 조금이라도 익숙해진건지 재미있긴 하다 ㅎㅎㅎㅎ 그래도 골드 들어가면 bfs도 인정사정 없이 어려워지겠지??! 화이팅 쟤스민 할 쑤 있숴!!