문제

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . 5 . . . . . |
4 * * * * . 4 * * * * |
3 . . . . . . 3 . . . . | .
2 . . . . . . 2 . . . . | .
1 . C . . . . 1 . C . . | .
0 . . . . . . . 0 . -------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

.: 빈 칸
*: 벽
C: 레이저로 연결해야 하는 칸
'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

예제

예제 입력 1

7 8

.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1

3

---

풀이

bfs문제이지만 고려해야할 조건이 있다. 흔히 bfs는 어떤 두 점 사이의 최소거리 값을 구하는 문제이지만 이번의 경우에는 조금 다르게 두 'C' 사이의 거리에 놓인 거울개수의 최소값을 구하는 것이다. 즉, 'C'에서 다른 'C'로 이동하여 갈 때 이미 방문했는지 안했는지가 중요한게 아니라 거울개수가 최소인지가 중요한것이다. 또한 어느 한 점으로 들어오는 빛은 방향성을 가지기 때문에 동,서,남,북으로 진행하는 빛은 본인이 진행하는 방향의 빛을 제외하고는 거울이 필요하다는 것이다.

풀이 로직
1. 큐를 먼저 구현한다.
2. 시작점 'C'에서 출발하는 네 가지 방향의 빛을 초기값을 세팅한다.
3. 큐에서 하나 꺼낸다.
3-1. 진행중인 빛의 방향과 다르다면 거울의 개수를 +1
3-2. 진행중인 빛의 방향과 같다면 거울의 개수는 그대로 둔다.
4. 다음 점의 거울개수보다 작거나 같다면 큐에 삽입한다.
5. 큐에 남은게 없을 때까지 3~4를 반복한다.

const [[W, H], ...map] = require('fs')
  .readFileSync('./dev/stdin')
  .toString()
  .trim()
  .split("\n")
  .map((el, idx) => (idx ? el.split("") : el.split(" ").map(Number)));

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.rear = null;
    this.length = 0;
  }

  isEmpty() {
    if (this.length === 0) return true;
    return false;
  }

  enqueue(data) {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return false;

    const answer = this.head.data;
    this.head = this.head.next;
    this.length--;

    return answer;
  }
}

const visited = Array.from({ length: H }, () => new Array(W).fill(Infinity));
const posC = [];

for (let i = 0; i < H; i++) {
  for (let j = 0; j < W; j++) {
    if (map[i][j] === "C") posC.push([i, j]);
  }
}
const [startR, startC] = posC[0];
const [endR, endC] = posC[1];
visited[startR][startC] = 0;

const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

const queue = new Queue();
for (let i = 0; i < 4; i++) {
  queue.enqueue([startR, startC, i, 0]);
}

while (!queue.isEmpty()) {
  const [curR, curC, dir, mir] = queue.dequeue();

  for (let i = 0; i < 4; i++) {
    const [nextR, nextC] = [curR + dr[i], curC + dc[i]];
    let nextMir = mir;
    // 주어진 맵 범위를 초과한 경우는 패스
    if (nextR < 0 || nextC < 0 || nextR >= H || nextC >= W) continue;
    // 벽인 경우는 패스
    if (map[nextR][nextC] === "*") continue;
    // 현재 진행중인 방향과 다르다면 거울 +1
    if (dir !== i) nextMir++;
    if (visited[nextR][nextC] >= nextMir) {
      queue.enqueue([nextR, nextC, i, nextMir]);
      visited[nextR][nextC] = nextMir;
    }
  }
}

console.log(visited[endR][endC]);