백준 1303: 전쟁 - 전투 - javascript(dfs)

문제 출처 

https://www.acmicpc.net/problem/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

문제 풀이 힌트 

dfs를 활용한다. 

- 방문하지 않는 좌표일 때 dfs함수로 방문할 수 있다. 

- 뭉쳐있는 아군 혹은 적군 수 따로 구하고, 그 수를 제곱해서 합한 수도 따로 구한다. 

- 대각선은 뭉쳐있는 것이 아니다. (사방면만 확인)

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [N,M] = input.shift().split(' ').map(v => +v); 
const graph = Array.from({length: M}).map(() => []); //빈 graph 생성 
for(let i=0; i<M; i++){
    graph[i] = input[i].split('') //빈 graph에 병사들 삽입 
}
const visited = Array.from({length: M}).map(() => new Array(N).fill(false)); //방문한 그래프 좌표인지 체크하는 배열 생성 

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

let tempW = 0; //뭉쳐있는 아군
let tempB = 0; //뭉쳐있는 적군
function dfs(y, x, soldier){
   visited[y][x] = true; //방문 체크  
   if(soldier === 'W') tempW++; //아군일 때 뭉쳐있는 아군 수 +1
   else if(soldier === 'B') tempB++; //적군일 때 뭉쳐있는 적군 수 +1; 
    
    for(let i=0; i<4; i++){ //왼, 오, 아, 위
        let nx = x + dx[i];
        let ny = y + dy[i]; 
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue; //그래프 영역 벗어나는 좌표 pass 
        if(!visited[ny][nx] && graph[ny][nx] === soldier){ //방문하지 않는 좌표 && (아군끼리 적군끼리인지 확인)
                 dfs(ny, nx, soldier)
        }
    }
}

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'){ //아군일 때 
                dfs(i,j, 'W')
                white += (tempW* tempW) //제곱한 것을 white에 더해준다. 
                tempW = 0;  //초기화 
            }else if(graph[i][j] === 'B'){ //적군일 때 
                dfs(i,j, 'B')
                blue += (tempB * tempB) //제곱한 것을 blue에 더해준다. 
                tempB = 0; //초기화 
                     }
        }  
    }
}
console.log(white, blue)

Only 문제 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [N,M] = input.shift().split(' ').map(v => +v); 
const graph = Array.from({length: M}).map(() => []); 
for(let i=0; i<M; i++){
    graph[i] = input[i].split('')
}
const visited = Array.from({length: M}).map(() => new Array(N).fill(false)); 

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

let tempW = 0; 
let tempB = 0; 
function dfs(y, x, soldier){
   visited[y][x] = true; 
   if(soldier === 'W') tempW++; 
   else if(soldier === 'B') tempB++; 
    
    for(let i=0; i<4; i++){
        let nx = x + dx[i];
        let ny = y + dy[i]; 
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue; 
        if(!visited[ny][nx] && graph[ny][nx] === soldier){
                 dfs(ny, nx, soldier)
        }
    }
}

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'){
                dfs(i,j, 'W')
                white += (tempW* tempW)
                tempW = 0; 
            }else if(graph[i][j] === 'B'){
                dfs(i,j, 'B')
                blue += (tempB * tempB)
                tempB = 0;
                     }
        }  
    }
}
console.log(white, blue)