[알고리즘] 백준 1303 - 전쟁 - 전투 (JS)

✅ 문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? (단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.)

✅ 조건

시간 제한	메모리 제한
2 초	128 MB

✅ 입력

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

✅ 출력

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

✅ 풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");

// 아군 - 흰색옷(W) , 적군 - 파란색옷(B)
// 병사 N 명이 뭉쳐있을 때 N^2 의 위력 낼 수 있음. (대각선으로만 인접한 경우는 뭉쳐있는 것 아님.)

const [N, M] = input[0].split(" ").map(Number);
const info = input.slice(1, input.length);
const map = [];
const visited = [];
let [white, blue] = [0, 0];

// 탐색 방향 - 상 하 좌 우
const dx = [0, 0, -1, 1];
const dy = [-1, 1, 0, 0];

for (let i = 0; i < M; i ++) {
    visited.push([]);

    for (let j = 0; j < N; j ++) {
        visited[i].push(0);
    }
}

for (const [i ,row] of info.entries()) {
    const item = row.split("");
    map.push([]);
    for (const s of item) {
        map[i].push(s);
    }
}

function BFS(x, y) {

    const queue = [];
    queue.push([x, y]);
    visited[x][y] = 1;
    let nt = map[x][y];
    let answer = 0;

    while (queue.length > 0) {
        const [cx, cy] = queue.shift();
        answer += 1;

        for (let i = 0; i< 4; i ++) {
            const nx = cx + dx[i];
            const ny = cy + dy[i];

            if(nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if(visited[nx][ny] === 0 && map[nx][ny] === nt) {
                    visited[nx][ny] = 1;
                    queue.push([nx, ny]);
                }
            }
        }
    }

    nt === "W" ? (white += answer ** 2) : (blue += answer ** 2);
}

for (let i = 0; i < M; i ++) {
    for (let j = 0; j < N; j ++) {
        if (!visited[i][j]) BFS(i, j);
    }
}

// 내 병사의 위력의 합 적국 병사의 위력의 합을 출력.
console.log(white, blue);

 

bfs 알고리즘을 이용해서 풀이했다. 자바스크립트에는 큐 자료구조가 내장되어 있지 않다. 이 문제는 시간복잡도 제한이 널널한 편이라서 Array를 사용해서 bfs를 구현했다. (shift() 메서드 사용 시 배열의 맨 앞 원소를 제거한다. → dequeue와 유사.) 하지만 실제 시간복잡도는 queue보다 커지므로 앞으로는 구현해서 사용하자.

 

문제로 돌아오면 간단한 탐색 문제지만 “대각선으로 인접한 병사들은 뭉쳐있지 않은 것으로 판단한다.” 라는 말의뜻 을 잘못 이해해서 조금 헤맸다. [상, 하, 좌, 우]로 탐색하며 같은 편의 병사가 있을 때 answer += 1 해주고, 큐가 비었을 때 answer ** 2 를 총 위력에 더하여 출력해준다.

• for .. of 구문에서 인덱스를 사용하는 방법에 대해 알았다.
• JS를 사용해서 BFS 알고리즘을 구현했다.
• JS를 사용해서 queue 자료구조를 구현했다.