쉬운 최단거리

쉬운 최단거리

문제 설명

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

📥 예제 입력

```
15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
```

📤 예제 출력

```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34
```

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
    const [N, M] = input[0].split(" ").map(Number)
    let arr = input.slice(1).map((line) => line.split(" ").map(Number));
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    let startX = 0
    let startY = 0
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (arr[i][j] === 2) {
                startX = i
                startY = j
            }
        }
    }
    const newArr = Array.from({ length: N }, (_, i) =>
  Array.from({ length: M }, (_, j) => (arr[i][j] === 0 ? 0 : -1))
);

    const bfs = () => {
        let queue = [[startX, startY, 0]]
        let head = 0

        newArr[startX][startY] = 0

        while(queue.length > head) {
            let [x, y, cnt] = queue[head++]

            for (let k = 0; k < 4; k++) {
                let nx = x + dx[k]
                let ny = y + dy[k]

                if (0 <= nx && nx < N && 0 <= ny && ny < M && newArr[nx][ny] === -1 && arr[nx][ny] !== 0) {
                    newArr[nx][ny] = cnt + 1
                    queue.push([nx, ny, cnt+1])
                }
            }
        }
    }
    bfs()

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (arr[i][j] !== 0 && newArr[i][j] === -1) {
                // 도달 불가 칸만 -1로 표시
                newArr[i][j] = -1
            }
    }
}


    for (let i = 0; i < N; i++) {
    console.log(newArr[i].join(' '));
}

}
solution(input)

아이디어 / 접근법

1. 2의 위치 찾기
2. 새로운 배열 만들기
3. BFS 돌리면서 새 배열에 기록하기

후기

금방 생각해서 정답이 쉽게 나오길래 바로 제출했는데 3%에서 자꾸 틀리더라 알고보니까 출력 방식이 달라서 그랬었다...