[백준 알고리즘] 1303번 전쟁 - 전투(Java) 문제 풀이

문제

https://www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

문제에 대한 이해

그래프 이론에서 DFS를 이용한 풀이를 이용해보면 된다.

이 문제의 경우 영역과 관련된 문제에서 DFS를 이용한 문제들과 많은 연관이 있었다.

그래서 어렵게 풀지는 않았다.

어떻게 풀 것인가?

DFS에서 많이 쓰이는 패턴을 쓰면 된다.

이는 코드를 보면 알게된다.

W의 영역을 찾아서 제곱하여 값에 더하고

B의 영역을 찾아서 제곱하여 값에 더하고를

모든 영역이 방문 될때까지 계산하면 완료된다.

시간복잡도

O(N)

공간복잡도

O(N^2)

풀면서 놓쳤던점

크게 없었지만 그래도 뭔가 개선할 점은 있는 코드라는 생각은 든다.

이 문제를 통해 얻어갈 것

인접행렬을 이용한 DFS

내 코드 

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

// 백준알고리즘 1303번 전쟁 - 전투

public class Main {
    static int N, M, nowX, nowY;
    static char[][] arr;

    static boolean[][] visit;
    static int[] dirX = {0, 0, -1, 1}; // 상 하 좌 우
    static int[] dirY = {-1, 1, 0, 0}; // 상 하 좌 우
    static int sum_B, sum_W;


    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];
        visit = 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);
            }
        }

        int result_W = 0;
        int result_B = 0;

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visit[i][j] && arr[i][j] == 'W') {
                    sum_W = 1;
                    DFS_W(i, j);
                    result_W += (sum_W * sum_W);
                }
                if (!visit[i][j] && arr[i][j] == 'B') {
                    sum_B = 1;
                    DFS_B(i, j);
                    result_B += (sum_B * sum_B);
                }
            }
        }
        System.out.println(result_W + " " + result_B);

    }

    static void DFS_W(int x, int y) {
        visit[x][y] = true;

        for (int i = 0; i < 4; i++) {
            nowX = dirX[i] + x;
            nowY = dirY[i] + y;

            if (range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 'W') {
                sum_W++;
                DFS_W(nowX, nowY);
            }
        }

    } // End of DFS

    static void DFS_B(int x, int y) {
        visit[x][y] = true;

        for (int i = 0; i < 4; i++) {
            nowX = dirX[i] + x;
            nowY = dirY[i] + y;

            if (range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 'B') {
                sum_B++;
                DFS_B(nowX, nowY);
            }
        }

    } // End of DFS

    static boolean range_check() {
        return (nowX >= 0 && nowY >= 0 && nowX < M && nowY < N);
    } // End of range_check
}