1303 전쟁-전투 (Java)

전쟁 - 전투

문제

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

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

입력

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

출력

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

풀이

각각의 위치에서 bfs를 통해 몇명의 같은팀의 병사가 있는지 확인한다.
bfs진행 과정은 다음과 같다.

1. 시작 노드를 큐에 넣는다.
2. 큐에서 노드를 하나 뺀 후 상하좌우를 확인하여 자신과 같은 팀일 경우 큐에 넣는다.
3. 2번을 큐가 빌때까지 반복한다.

bfs를 사용할 때 주의할 점은 방문처리를 통하여 반복을 없애야 하는 것인데 이는 다른 2차원 boolean배열을 선언하여 큐에 넣을때 체크하는 방식으로 해결했다.

코드

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 Main{

    static int n;
    static int m;
    static char[][] graph;
    static boolean[][] isVisited;

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


    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());

        graph = new char[n][m];
        isVisited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String s = br.readLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = s.charAt(j);
            }
        }

        int team1 = 0;
        int team2 = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!isVisited[i][j]) {
                    if (graph[i][j] == 'W') {
                        team1 += bfs(i, j);
                    }else{
                        team2 += bfs(i, j);
                    }
                }
            }
        }
        System.out.println(team1 + " " + team2);

    }

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static int bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        isVisited[x][y] = true;
        char team = graph[x][y];
        int ret = 0;

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            ret++;

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;

                if(isVisited[nx][ny] || graph[nx][ny] != team)
                    continue;

                isVisited[nx][ny] = true;
                queue.add(new Point(nx, ny));

            }
        }

        return (int)Math.pow(ret, 2);
    }
}