[BOJ] 1303 - 전쟁 - 전투

-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제 설명

www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

난이도: 실버 1

사용 언어: JAVA

 

전쟁터에서 전쟁이 벌어지고 있습니다. 흰 옷을 입은 아군과, 파란 옷을 입은 적군이 뒤섞여 전투를 벌이고 있습니다. 그런데 같은 팀 군인들끼리 뭉쳐있으면, 뭉쳐있는 사람들의 수만큼 전투력이 증가하게 됩니다. N명이 뭉쳐있다면, N^2의 전투력을 발휘할 수 있습니다. 뭉쳐있다는 것은 한 병사의 상하좌우에 다른 병사가 존재하는 경우를 뜻합니다.

 

만일 한 명만 혼자 있다면 전투력은 1이지만, 세명이 뭉쳐있으면 9의 전투력을 발휘할 수 있습니다. 대각선에 존재하는 아군은 뭉쳐있다고 간주하지 않습니다. 이때, 아군과 적군의 총 전투력을 각각 출력하면 됩니다.

 

 

위와 같은 예제에서는 W로 표시된 흰 옷을 입은 아군이 각각 9명, 7명씩 뭉쳐있기 때문에 130의 전투력을, B로 표시된 적군이 각각 1명, 8명씩 뭉쳐있기 때문에 65의 전투력을 발휘할 수 있습니다.

 

풀이 

이 문제는 DFS나 BFS 등 그래프 탐색 알고리즘을 사용하면 해결할 수 있습니다. 저는 DFS를 이용해 문제를 해결하였습니다.

 

입력을 이차원 배열에 집어넣고, (0,0)에서 가장 우측 하단까지 반복문을 돌면서, W인 칸은 W만 검사하는 DFS를 돌고, B인 칸은 B만 검사하는 DFS도는 코드를 재귀 함수를 통해 구현했습니다. 한 번의 DFS를 탈출할 때마다 결괏값에 카운팅 한 숫자를 제곱해서 더해주었습니다.

 

(0,0)에서 시작하는 한 차례의 DFS만 그림으로 단계를 따라가보도록 하겠습니다. 한 번 검사한 병사를 다시 검사하지 않도록, 한 번 검사한 뒤에는 0으로 바꿔주었습니다.

 

이런 식으로 0이 아닌 칸을 검사하는 방법으로 마지막 칸까지 검사를 진행합니다.

 

import java.io.*;
import java.util.StringTokenizer;
 
class Main {
 
    static int N, M;
    static int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 인접한 방향 4가지
    static int white_cnt = 0, blue_cnt = 0;
 
    public static void dfs(int x, int y, char arr[][], char color) {
        int i;
        for (i = 0; i < 4; i++) {
            if (x + d[i][0] >= 0 && x + d[i][0] < M && y + d[i][1] >= 0 && y + d[i][1] < N) { // 배열의 범위를 벗어나는지 확인
                if (color == 'W' && arr[x + d[i][0]][y + d[i][1]] == 'W') { // W 일때 만 도는 DFS
                    arr[x + d[i][0]][y + d[i][1]] = '0';
                    white_cnt++; // 뭉쳐있는 아군의 수를 카운팅
                    dfs(x + d[i][0], y + d[i][1], arr, 'W');
                } else if (color == 'B' && arr[x + d[i][0]][y + d[i][1]] == 'B') { //B 일때만 도는 DFS
                    arr[x + d[i][0]][y + d[i][1]] = '0';
                    blue_cnt++; // 뭉쳐있는 적군의 수를 카운팅 
                    dfs(x + d[i][0], y + d[i][1], arr, 'B');
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        char[][] arr = new char[M][N];
        int i, j;
        for (i = 0; i < M; i++) {
            s = br.readLine();
            for (j = 0; j < N; j++) {
                arr[i][j] = s.charAt(j);
            }
        }
        char color;
        int white_result = 0;
        int blue_result = 0;
        for (i = 0; i < M; i++) {
            for (j = 0; j < N; j++) {
                if (arr[i][j] != '0') {
                    color = arr[i][j];
                    if (color == 'W')
                        white_cnt++;
                    else
                        blue_cnt++;
                    arr[i][j] = '0';
                    dfs(i, j, arr, color);
                    white_result += white_cnt * white_cnt; // 반복문을 한 번 돌 때마다 result값에 추가된 전투력을 더해줌
                    blue_result += blue_cnt * blue_cnt;
                    white_cnt = 0;
                    blue_cnt = 0;
                }
            }
        }
        System.out.print(white_result + " ");
        System.out.println(blue_result);
    }
}