[백준_1303] 전투

문제

백준 1303번
https://www.acmicpc.net/problem/1303

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

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

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

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

• 생각해보기

Code

• char로 board(전쟁터)를 만들어준다.
• isVisited(병사 확인)를 전쟁터의 크기만큼 만들어준다.
• 이중 for문을 통해 현재 위치의 병사가 확인이 되었다면 continue를 해준다.
• 병사의 어느 쪽인지 판단되지 않았을 경우 bfs를 통해 주변 자신과 같은 병사들을 판단한다.
• bfs의 queue를 통해 현재 병사의 위치에서 상, 하, 좌, 우의 병사들을 확인다.
• 그 중 전쟁터를 벗어나거나 상, 하, 좌, 우 이동했을 때 병사가 확인이 된 경우라면 continue를 해준다.
• 위치를 이동했을 때 병사가 확인이 되지 않았을 경우 처음 bfs에 시작한 병사의 옷색과 같다면 cnt를 하나씩 늘려주고 queue에 다시 넣어주면서 isVisited에 병사 확인이 되어 true로 바꾸어준다.
• 그리고 입력된 병사가 'W'라면 나의 팀 병사이므로 resultMy(나의 팀 위력 합)에다 더해준다.
• 반대로 'W'가 아닌 'B'일 경우 resultYou(적의 팀 위력 합)에다 더해준다.
• 위 이중 for문부터 반복하면서 전쟁터 판에 있는 모든 병사들이 어느 쪽 병사인지 확인이 되었다면 최종적으로 resultMy와 resultYou의 결과를 반환한다.

Java

import java.io.*;
import java.util.*;

class Node { // 위치 노드
    int x;
    int y;

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

public class Main {
    static int N, M;
    static int[] dX = {0, 1, 0, -1}; // x축 이동
    static int[] dY = {1, 0, -1, 0}; // y축 이동
    static char[][] board; // 전쟁터
    static boolean[][] isVisited; // 병사 확인
    static int resultMy = 0; // 나의 병사 위력 합
    static int resultYou = 0; // 적의 병사 위력 합
    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()); // 전쟁터 세로

        board = new char[M][N];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            String s = st.nextToken();
            for (int j = 0; j < s.length(); j++) {
                board[i][j] = s.charAt(j);
            }
        }

        isVisited = new boolean[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 어느 쪽 병사인지 확인 되었을 경우
                if (isVisited[i][j]) {
                    continue;
                }
                bfs(i, j);
            }
        }
        System.out.println(resultMy + " " + resultYou);
    }

    public static void bfs(int i, int j) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(i, j));
        isVisited[i][j] = true; // 현재 병사가 어느쪽인지 확인

        int cnt = 1;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            for (int k = 0; k < dX.length; k++) {
                // 다음 위치의 병사 위치
                int x = cur.x + dX[k];
                int y = cur.y + dY[k];

                // 전쟁터 크기를 벗어나거나 다음 병사가 이미 확인된 병사일 경우
                if (x < 0 || y < 0 || x >= M || y >= N || isVisited[x][y]) {
                    continue;
                }

                // 처음에 입력된 병사 옷색과 이동한 병사의 옷색이 같을 경우
                if (board[i][j] == board[x][y]) {
                    cnt++;
                    queue.offer(new Node(x, y));
                    isVisited[x][y] = true;
                }
            }
        }

        // 입력된 병사의 옷색이 'W'일 경우(나의 팀)
        if (board[i][j] =='W') {
            resultMy += Math.pow(cnt, 2);
        } else {
            resultYou += Math.pow(cnt, 2);
        }
    }
}