[ JavaScript (Node.js) ] 백준 실버1 1303번 전쟁-전투

전쟁-전투 #1303

 

전쟁 - 전투

 

문제

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

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

입력

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

출력

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

예제 입력 1

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

예제 출력 1 

130 65​

풀이 

// 전쟁-전투
// https://www.acmicpc.net/problem/1303

// 입력값 처리
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
const [N, M] = input[0].split(" ").map((i) => parseInt(i));

const graph = Array.from({ length: M }, (_, i) => input[i + 1]); // B/W 저장 배열

const visited = Array.from({ length: M }, () => Array(N).fill(false)); // 방문 배열 초기화

const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];

let white = 0; // 우리 팀의 전력
let blue = 0; // 적팀의 전력

for (let i = 0; i < M; i++) {
  for (let j = 0; j < N; j++) {
    if (!visited[i][j]) {
      if (graph[i][j] === "W") {
        white += BFS(i, j);
      } else if (graph[i][j] === "B") blue += BFS(i, j);
    }
  }
}

console.log(white, blue);

// BFS

function BFS(x, y) {
  const queue = [[x, y]];
  let count = 1;
  visited[x][y] = true;
  while (queue.length > 0) {
    const [curX, curY] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const nextX = curX + dx[i];
      const nextY = curY + dy[i];

      if (
        nextX >= 0 &&
        nextY >= 0 &&
        nextX < M &&
        nextY < N &&
        !visited[nextX][nextY] &&
        graph[curX][curY] === graph[nextX][nextY]
      ) {
        count++;
        visited[nextX][nextY] = true;
        queue.push([nextX, nextY]);
      }
    }
  }

  return count ** 2;
}

설명

너비 우선 탐색 (BFS)로 문제를 해결하였다.

1. N, M을 저장한다.
2. 각각의 "B"와 "W"을 저장할 이차원 배열 graph를 저장한다.
3. 총 크기 M*N의 방문 배열 visited를 초기화한다. 
4. BFS에서 탐색 방향(상, 우, 하, 좌)을 dx(x좌표의 방향), dy(y좌표의 방향)에 저장한다.
5. 최종적으로 출력될 값인 white(우리 팀의 전력 ), blue(상대 팀의 전력) 변수를 0으로 초기화한다. 
6. 이중 for문으로 graph 배열을 돌면서,
   1. 해당 좌표의 칸을 방문하지 않았으면서 W이면 BFS에 현재의 좌표를 파라미터로 주고, 리턴값을 white에 저장한다.
   2. 해당 좌표의 칸을 방문하지 않았으면서 B이면 BFS에 현재의 좌표를 파라미터로 주고, 리턴값을 blue에 저장한다. 

BFS 함수를 선언한다.

1. 파라미터로 받은 x,y (탐색할 첫 노드의 좌표)를 큐에 넣는다.
2. 최종 제곱하여 리턴할 변수 count를 1로 초기화해준다.
   0 이 아닌 1인 이유는 이미 첫 노드를 탐색함으로써 전력이 1이 있는 것이다.
3. 방문배열의 x,y를 true로 바꾸어 방문한 노드임을 저장한다. 
4. 큐가 크기가 0이면 반복한다. (큐에 하나의 노드라도 존재한다면) 
5. 큐의 가장 앞 노드를 꺼낸다(shift) 
   1. 상, 우, 하, 좌 방향으로 탐색한다. 
   2. 탐색할 좌표가 배열의 범위 안에 유효하고 방문하지 않은 노드이면서 이전 탐색한 값(B 또는 W)과 같으면 같은팀인 것이므로 count를 1증가시키고, 방문배열을 true로 바꾸며, 큐에 푸시한다. 
6. 전력이 제곱한 값만큼 더해진다고 했으므로, count를 제곱하여 리턴한다. 

 

문제의 테스트 케이스는 통과하지만, 틀린 경우 체크해야 할 것 ✔️

처음 문제를 제출하고나서, 문제에 나왔던 테스트 케이스는 통과하지만, 9%만에 문제가 틀렸다고 나왔다. 

테스트 케이스도 잘 통과했고, 파일 이름 오류도 아닌데 왜 ..?

문제를 잘 읽어보니 입력을 주어지는 N과 M이 각각 가로, 세로의 크기를 뜻하는 것이었다.

나는 습관적으로 배열을 만들 때에 N과 M을 각각 행의 크기, 열의 크기로 생각하여 문제를 진행해서 틀린 것이었다.

테스트 케이스는 정사각형으로 주어졌기 때문에 이 문제를 파악하지 못한 것  🫠

사소한 것들도 잘 읽어야 겠다 ... ~ 

 

문제를 잘 읽자 !!