[백준] 1303 전쟁 - 전투 Node.js (BFS 풀이)

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N²의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

예제 입력 1

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1

130 65

---

문제풀이

💡 문제풀이 과정

• 같은 팀의 N명이 뭉쳐있을 때는 N²의 위력을 낼 수 있다고 하였다. 따라서 인접한 네방향(상하좌우)에 뭉쳐있는 병사들과 따로 1명씩 떨어져있는 병사들을 각각 따로 카운팅하는 것이 핵심이었다. 하지만 주어진 입력값은 ‘W’와 ‘B’만으로 이루어져 있다. 즉 그 이외의 값이 없기때문에, 팀 단위와 한 명 단위를 각각 세지 않고 모든 인원을 합산하여 카운팅하는 문제가 발생하였다.
• 위 문제를 해결하기위해 방문 체크를 할 visited 배열을 만드는 대신에 입력값을 받은 field라는 2차원 배열을 만들고 방문한 곳은 값을 0으로 넣어주기로 했다. 그리고 현재 위치의 값과 다음에 이동할 인접한 네방향 위치의 값이 같으면 이라는 조건을 추가하여 병사들이 근처에 붙어있는지를 확인한다.

✅ 답안 : BFS - queue 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input.shift().split(' ').map(Number);
const field = input.map((v) => v.split(''));
const dir = [[0, 1], [0, -1], [-1, 0], [1, 0]]; // 인접한 상하좌우 x,y좌표
let [white, blue] = [0, 0];

const bfs = (x, y) => {
  let cnt = 0;
  const queue = [[x, y]];
  const team = field[x][y]; // 현재 값
  field[x][y] = 0; // 방문 처리

  while (queue.length) {
    const [cx, cy] = queue.shift();
    cnt++; // 병사 수 증가

    for (let i = 0; i < 4; i++) {
      const nx = cx + dir[i][0];
      const ny = cy + dir[i][1];
      
      // 전쟁터 밖으로 벗어나지 않았고, 현재값과 다음 인접한 위치의 값이 같은 경우
      if (nx >= 0 && nx < M && ny >= 0 && ny < N && field[nx][ny] == team) {
        field[nx][ny] = 0; // 방문 처리
        queue.push([nx, ny]);
      }
    }
  }
  // 현재 위치의 값이 'W'이면 white에 'B'이면 blue에 카운팅한 값의 제곱값 더하기
  team == 'W' ? (white += cnt ** 2) : (blue += cnt ** 2);
};

for (let i = 0; i < M; i++) {
  for (let j = 0; j < N; j++) {
    // 해당 값이 0이 아닌 경우(방문하지 않은 경우) BFS 실행
    if (field[i][j]) bfs(i, j);
  }
}

console.log(white + ' ' + blue);