🧑🏻‍💻 문제

💡문제 분석 요약

• 문제 내에서 주어지는 배열의 요소엔 W 와 B 가 들어가 있다.
• 인접해 있는 같은 요소끼리 있을 때 그 값의 제곱을 하여 최종적으론 각 요소끼리 제곱한 합을 구한다.

💡알고리즘 설계

• DFS 를 통해 모든 배열을 돌면서 각 요소의 합을 구한다.
• 여기서 중요한 건 요소가 W 와 B 두 개가 있기 때문에 각 요소끼리 덧셈을 따로 진행해야 한다.
• 기존의 DFS 코드에 color 값에 대한 정보를 넘겨, 값을 체크할 때 해당 color인지 확인할 수 있게 한다.

💡코드

public class 백준_1303_전투 {
    static char[][] arr; // 문제에서 주어지는 전쟁터 배열을 저장
    static boolean[][] visited; // 방문 처리 배열
    static int[] dx = {1, 0, -1, 0}; // 상하좌우 움직임을 위한 요소
    static int[] dy = {0, 1, 0, -1};
    static int M; // 전쟁터의 가로 크기
    static int N; // 전쟁터의 세로 크기
    static int count = 0;
    static int wCount = 0; // W 수를 담을 변수
    static int bCount = 0; // B 수를 담을 변수

    private static void DFS(int a, int b, char color) { // color 을 매개변수로 받는다!
        visited[a][b] = true;
        count +=1;

        for (int i =0; i < 4; i++) {
            int newA = a + dx[i];
            int newB = b + dy[i];

            // 이동한 곳이 매개변수로 들어온 color 와 같은지 함께 확인
            if (newA >= 0 && newA < M && newB >=0 && newB < N && arr[newA][newB] == color) {
                if (!visited[newA][newB]) {
                    DFS(newA, newB, arr[newA][newB]);
                }
            }
        }
    }

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new char[M][N];
        visited = new boolean[M][N];

        for (int i = 0; i < M; i++) {
            String str = br.readLine();

            for (int j = 0; j < N; j++) {
                arr[i][j] = str.charAt(j);
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j]) {
                    char color = arr[i][j];
                    count = 0; // 새로운 DFS를 돌 때마다 color가 달라질 수 있으므로 count를 여기서 초기화 해줌.
                    DFS(i, j, color);

                    if (color == 'W') { // DFS 가 완료된 후 어떤 컬러에서 탐색되어 나온 건지에 따라 나눠서 진행
                        wCount += count * count;
                    }
                    else {
                        bCount += count * count;
                    }
                }
            }
        }
        System.out.println(wCount + " " + bCount);
    }
}

💡시간복잡도

• M N 배열에 대해 DFS 탐색을 진행하므로 O(NM) 이다.

💡 느낀점 or 기억할정보

• 2개 이상의 값을 체크할 때 DFS에 해당 요소를 매개변수로 넘겨 활용한다!