[BOJ] 1303. 전쟁 - 전투

문제

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

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

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

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

해결 방법

• dfs나 bfs를 사용하는 문제
• 전쟁터는 이차원 배열로 선언한다.
• 방문도 이차원 배열로 선언한다.
• 전체 배열을 탐색하면서 방문하지 않은 위치라면 dfs를 한다.
• dfs를 하면 그 위치를 방문처리 하고 병사의 수 count를 +1한다.
• 그 위치의 상하좌우를 탐색하여 같은 색이 있으면 dfs를 한다(재귀).
• 더이상 주변에 같은 색이 없으면 count * count를 하고 내 병사인지 적국의 병사인지 확인하여 result에 각 count^2를 추가한다.

코드

// 전쟁 - 전투
public class Week08_1303 {
    static String[][] map;
    static boolean[][] visited;
    static int[] dx = {0, -1, 0, 1}; // 상좌하우
    static int[] dy = {-1, 0, 1, 0};
    static int w;
    static int h;
    static int count = 0;
    static int whiteRes = 0;
    static int blueRes = 0;

    public static void main(String[] args) throws IOException {
        input();
        solve();
        output();
    }

    private static void output() {
        StringBuilder sb = new StringBuilder();
        sb.append(whiteRes);
        sb.append(" ");
        sb.append(blueRes);
        System.out.println(sb);
    }

    private static void solve() {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!visited[i][j]){
                    dfs(i, j);
                    int square = count * count;
                    if (map[i][j].equals("W")) {
                        whiteRes += square;
                    }
                    if (map[i][j].equals("B")) {
                        blueRes += square;
                    }
                    count = 0; // 다른 뭉쳐있는 곳의 count를 세기 위해 초기화한다.
                }
            }
        }
    }

    private static void dfs(int col, int row) {
        visited[col][row] = true;
        String color = map[col][row];
        count++;
        for (int i = 0; i < 4; i++) {
            int newH = col + dy[i];
            int newW = row + dx[i];
            if (newH >= 0 && newW >= 0 && newH < h && newW < w) {
                if (!visited[newH][newW] && map[newH][newW].equals(color)) {
                    dfs(newH, newW);
                }
            }
        }
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        map = new String[h][w];
        visited = new boolean[h][w];

        for (int i = 0; i < h; i++) {
            String[] temp = br.readLine().split("");
            for (int j = 0; j < temp.length; j++) {
                map[i][j] = temp[j];
            }
        }
    }
}