[백준] 1303번 : 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다.

그러나 당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.

문제는, 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가?

단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다.

그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다.

모든 자리에는 병사가 한 명 있다. (B는 파랑, W는 흰색이다.)

출력

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

문제해결방법

배열을 탐색하며 BFS 또는 DFS를 사용해서 모여있는 병사들을 세고 N^2를 해당 팀에 더해준다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main1303_전쟁전투 {
 
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        char [][] map = new char[N][M];
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) map[i][j] = s.charAt(j);  
        }
        Queue<int[]> q = new LinkedList<>();
        int white = 0, blue = 0;
        for(int i=0; i<N; i++) {         
            for(int j=0; j<M; j++) {
                if(map[i][j]!='V') {
                    char team = map[i][j];
                    int count = 1;
                    q.add(new int[]{i, j});
                    map[i][j] = 'V';
                    while(!q.isEmpty()) {
                        int[] cur = q.poll();
                        for(int d=0; d<dir.length; d++) {
                            int xx = cur[0] + dir[d][0];
                            int yy = cur[1] + dir[d][1];
                            if(xx>=0 && xx<N && yy>=0 && yy<M && map[xx][yy]==team) {
                                map[xx][yy] = 'V';
                                count++;
                                q.add(new int[]{xx, yy});
                            }
                        }
                    }
                    if(team=='W') white += count*count;
                    else blue += count*count;
                }
            }  
        }
        System.out.println(white+" "+blue);
    }
 
}
 

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.