[JavaScript] 백준 코딩테스트 1303. 실버 1 : 전쟁 - 전투

📌  문제

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

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

📌  입력

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

📌  출력

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

📌  예제 입출력

---

📌  풀이

알아야 하는 것

• arr.reduce() : 배열의 각 요소에 대해 주어진 리듀서 함수를 실행하고 하나의 결과값을 반환한다.
  • 리듀서 함수는 누산기(arr), 현재 값(cur), 현재 인덱스(idx), 원본 배열(src) 4개의 인자를 가진다.
  • [0, 1, 2, 3, 4].reduce( (prev, curr) => prev + curr );
  • 0번 인덱스부터 3번 인덱스까지 누적된 값에 현재 값을 더하는 것으로 총 합 10이 나온다.
  • 리듀서 함수의 2번째 인자로 초기값을 설정하지 않으면 디폴트 0으로 실행된다.

구할 것

• BFS, DFS 모두 풀이 가능
• 기본 포맷
  • 전쟁터: input 첫 번째 줄에 주어진 가로 세로 값 
  • 병사들: 첫 번째 줄에 주어진 값 외의 모든 값
  • 중복 확인을 위한 visited 배열: 예제는 5 5 로 나와서 놓칠 수 있는데, 예컨대 5 4 라고 주어지면 전쟁터의 가로가 5고 세로가 4지만 배열 상에서는 5가 세로고 4가 가로라는 점을 헷갈리면 안된다.
  • (0, 0)부터 (4, 4)까지 이중 for문으로 순회할 때 해당 값이 W/B를 나눠서 bfs/dfs를 진행한다. 
  • bfs/dfs를 돌 때 queue나 stack에 넣어주고 방문처리 한 후 시작한 값 인근의 W/B를 찾을 때마다 power를 1씩 올려주고 bfs/dfs가 끝나면 그 값을 our/enemy에 push한다. 이 때 시작한 값 === 현재 값을 기준으로 상하좌우 좌표를 더해도 유효한 범위인지 확인해야 한다. 
  • 예제 값을 기준으로 하면 our = [9, 7], enemy = [1, 8]로 제곱한 후 더하면 81+49=130 / 1+64=65가 나온다
  • 이 누적 값을 구하기 위해 reduce()를 사용했다.  

const fs = require("fs");
const input = fs.readFileSync("./dev_stdin.txt").toString().trim().split("\n");

// 전쟁터
const [col, row] = input.shift().split(" ").map(Number);

// 병사들
const army = input.map((v) => v.split(""));

// 중복 확인
const visited = Array.from(Array(row), () => Array(col).fill(false));

const queue = [];
const our = [];
const enemy = [];

function bfs(startRow, startCol, color) {
  queue.push([startRow, startCol]);
  visited[startRow][startCol] = true;
  let power = 0;

  while (queue.length > 0) {
    const [currentRow, currentCol] = queue.shift();
    const dir = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ];

    for (let i = 0; i < 4; i++) {
      const nr = currentRow + dir[i][0];
      const nc = currentCol + dir[i][1];

      if (
        nr >= 0 &&
        nc >= 0 &&
        nr < row &&
        nc < col &&
        !visited[nr][nc] &&
        army[nr][nc] === color
      ) {
        queue.push([nr, nc]);
        visited[nr][nc] = true;
      }
    }
    power++;
  }
  if (color === "W") {
    our.push(power);
  } else {
    enemy.push(power);
  }
}

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (army[i][j] === "W" && !visited[i][j]) {
      bfs(i, j, "W");
    } else if (army[i][j] === "B" && !visited[i][j]) {
      bfs(i, j, "B");
    }
  }
}

let answer1 = our.reduce((sum, power) => sum + power * power, 0);
let answer2 = enemy.reduce((sum, power) => sum + power * power, 0);

console.log(answer1, answer2);

const fs = require("fs");
const input = fs.readFileSync("./dev_stdin.txt").toString().trim().split("\n");

// 전쟁터
const [col, row] = input.shift().split(" ").map(Number);

// 병사들
const army = input.map((v) => v.split(""));

// 중복 확인
const visited = Array.from(Array(row), () => Array(col).fill(false));

const stack = [];
const our = [];
const enemy = [];

function dfs(startRow, startCol, color) {
  stack.push([startRow, startCol]);
  visited[startRow][startCol] = true;
  let power = 0;

  while (stack.length > 0) {
    const [currentRow, currentCol] = stack.pop();
    const dir = [
      [-1, 0],
      [1, 0],
      [0, -1],
      [0, 1],
    ];

    for (let i = 0; i < 4; i++) {
      const nr = currentRow + dir[i][0];
      const nc = currentCol + dir[i][1];

      if (
        nr >= 0 &&
        nc >= 0 &&
        nr < row &&
        nc < col &&
        !visited[nr][nc] &&
        army[nr][nc] === color
      ) {
        stack.push([nr, nc]);
        visited[nr][nc] = true;
      }
    }
    power++;
  }
  if (color === "W") {
    our.push(power);
  } else {
    enemy.push(power);
  }
}

for (let i = 0; i < row; i++) {
  for (let j = 0; j < col; j++) {
    if (army[i][j] === "W" && !visited[i][j]) {
      dfs(i, j, "W");
    } else if (army[i][j] === "B" && !visited[i][j]) {
      dfs(i, j, "B");
    }
  }
}

let answer1 = our.reduce((sum, power) => sum + power * power, 0);
let answer2 = enemy.reduce((sum, power) => sum + power * power, 0);

console.log(answer1, answer2);