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

1303번: 전쟁 - 전투

---

[DFS or BFS]

2차원 배열이 map으로 주어지는 문제에서는 늘 BFS로 풀었어서 이번엔 DFS로 풀어보았다.

 

B와 W로 이루어진 지도를 char로 그대로 저장하지 않고 boolean으로 저장하였다. W 이면 true로, B이면 false로. 물론 char[][]로 저장하여도 상관없다.

 

이제 2차원 배열 모든 정점을 방문할 차례인데, B로 이루어진 덩어리와 W로 이루어진 덩어리의 개수를 Math.pow해서 반환하도록 했다.

 

DFS함수의 내부는 다음과 같이 인접한 정점을 방문할 때마다 cnt가 +1씩 되어 최종적으로 반환되는 cnt는 그 덩어리의 크기를 반환하게 된다.

    static int DFS(int y, int x, boolean isWhite){

        int cnt = 1;
        visit[y][x] = true;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx] || map[ny][nx] != isWhite) continue;

            cnt += DFS(ny, nx, isWhite);
        }

        return cnt;
    }

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n, m, white = 0, black = 0;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};
    static boolean[][] visit = new boolean[101][101], map = new boolean[101][101];

    static int DFS(int y, int x, boolean isWhite){

        int cnt = 1;
        visit[y][x] = true;

        for(int a=0; a<4; a++){
            int ny = y+Y[a];
            int nx = x+X[a];

            if(ny < 1 || nx < 1 || ny > n || nx > m || visit[ny][nx] || map[ny][nx] != isWhite) continue;

            cnt += DFS(ny, nx, isWhite);
        }

        return cnt;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();

            for(int j=1; j<=m; j++)
                map[i][j] = str[j-1] == 'W';
        }

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(!visit[i][j]){
                    if(map[i][j])
                        white += Math.pow(DFS(i, j, map[i][j]), 2);
                    else
                        black += Math.pow(DFS(i, j, map[i][j]), 2);
                }

        System.out.println(white + " " + black);
    }
}