[백준 / Java] 1303: 전쟁 - 전투 (BFS)

난이도: Silver 1

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

 

문제

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

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

입력

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

출력

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

---

 

2차원 배열 BFS 알고리즘의 기본 문제이다.

기본적으로 문제에서 주어진 배열을 입력받을 2차원 배열 ground를 선언하고,

방문 체크를 할 2차원 배열 visited를 선언하고, 

구역별 병사('W', 'B') 숫자를 세야 하니까 2차원 배열 count를 선언한다.

 

전체 2중 for문을 돌리면서,

해당 칸을 방문하지 않았고 해당 칸이 'W'일 때는 bfs 메서드에 인수로  i, j, 'W'를 넘겨주면 되고,

해당 칸을 방문하지 않았고 해당 칸이 'B'일 때는 bfs 메서드에 인수로 i, j, 'B'를 넘겨주면 된다. 

 

그리고 bfs 메서드에서는 가장 최근 방문한 x, y좌표에 해당하는 count 배열을 반환하여

반환받은 수의 제곱을 최종적으로 출력할 변수에 누적하면서 더하면 된다.

 

코드에 적힌 주석을 보면 바로 이해가 될 것이다.

자, 이제 코드를 보자.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class P1303_전쟁전투 {
    static int N, M;                    // 전쟁터의 가로, 세로 크기
    static int[] dx = {-1, 0, 1, 0};    // 상, 하 이동
    static int[] dy = {0, -1, 0, 1};    // 좌, 우 이동
    static char[][] ground;                // 2차원 전쟁터 배열
    static boolean[][] visited;            // 2차원 방문 배열
    static int[][] count;                // 2차원 병사의 수(= 위력) 배열
    
    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());    
        ground = new char[M][N];        // 세로(M, 행) x 가로(N, 열)
        visited = new boolean[M][N];
        count = new int[M][N];
        
        // 2차원 전쟁터 배열 초기화
        for (int i = 0; i < M; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                // 'W': 당신의 병사, 'B': 적국의 병사
                ground[i][j] = line.charAt(j);
            }
        }
        
        int myPower = 0;        // 당신의 병사 위력의 합
        int enemyPower = 0;        // 적국의 병사 위력의 합
        
        // 모든 칸을 탐색
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 해당 칸을 방문하지 않았고, 해당 칸에 당신의 병사가 있다면
                if (!visited[i][j] && ground[i][j] == 'W') {
                    // 해당 칸부터 bfs 수행하여 당신의 병사 수(= 위력)를 리턴받기
                    int count = bfs(i, j, 'W');    
                    // 당신의 병사 수의 제곱을 당신의 병사 위력의 합 변수에 더하기
                    myPower += count * count;
                }
                // 해당 칸을 방문하지 않았고, 해당 칸에 적국의 병사가 있다면
                if (!visited[i][j] && ground[i][j] == 'B') {
                    // 해당 칸부터 bfs 수행하여 적국의 병사 수(= 위력)을 리턴받기
                    int count = bfs(i, j, 'B');
                    // 적국의 병사 수의 제곱을 적국의 병사 위력의 합 변수에 더하기
                    enemyPower += count * count;
                }
            }
        }
        
        // 당신의 병사 위력의 합과 적국의 병사 위력의 합을 출력
        System.out.println(myPower + " " + enemyPower);
    }
    
    public static int bfs(int x, int y, char team) {
        Queue<Point> queue = new LinkedList<>();    // bfs 수행을 위한 큐
        int cnt = 1;    // 병사의 수(= 위력)
        
        queue.add(new Point(x, y));        // 현재 칸을 큐에 삽입
        visited[x][y] = true;            // 현재 칸을 방문 체크
        count[x][y] = cnt++;            // 현재 칸에 현재 병사의 수를 할당 후 1 증가
        
        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Point now = queue.poll();    // 현재 칸을 큐에서 뽑기
            
            // 현재 칸 기준으로 상, 하, 좌, 우 탐색
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                // 인접 칸의 x좌표나 y좌표가 유효한 인덱스 범위가 아니라면 건너뛰기
                if (nx < 0 || ny < 0 || nx >= M || ny >= N) {
                    continue;
                }
                
                // 인접 칸을 이미 방문했거나, 인접 칸이 다른 팀(병사)이라면 건너뛰기
                if (visited[nx][ny] || ground[nx][ny] != team) {
                    continue;
                }
                
                queue.add(new Point(nx, ny));    // 인접 칸을 큐에 삽입
                visited[nx][ny] = true;        // 인접 칸을 방문 체크
                count[nx][ny] = cnt++;        // 인접 칸에 현재 병사의 수를 할당 후 1 증가
                x = nx;        // 매개변수 x에 최근 방문한 x좌표 할당
                y = ny;        // 매개변수 y에 최근 방문한 y좌표 할당
            }
        }
        
        return count[x][y];        // 가장 최근 방문한 (x, y) 칸에 할당된 병사의 수 리턴
    }
    
    static class Point {
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}