[백준] 1303번 전쟁 - 전투 (Java)

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

1303번: 전쟁 - 전투

 

 

 

 

 

 

 

 

 

풀이 > 

그래프 탐색에서 큐를 사용해서 BFS 로 해결 가능하다. 

 

W, B 각각 병사에 대해 탐색하고 방문 표시를 해주면 된다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[] dirI = {1, -1, 0, 0};
    static int[] dirJ = {0, 0, 1, -1};
    static boolean[][] visited;
    static String[][] matrix;
    static int N;
    static int M;
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = reader.readLine().split(" ");
        
        M = Integer.parseInt(tmp[0]);
        N = Integer.parseInt(tmp[1]);
        matrix = new String[N][M];
        visited = new boolean[N][M];
        
        for(int i  = 0; i<N; i++) {
           matrix[i] = reader.readLine().split("");
        }
        
        int B = 0;
        int W = 0;
        Queue<int[]> queueB = new LinkedList<>();
        Queue<int[]> queueW = new LinkedList<>();
        
    
        for(int i = 0; i<N; i++) {
            for(int j = 0; j<M; j++) {
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    if ("B".equals(matrix[i][j])) {
                        queueB.add(new int[]{i, j});
                    } else {
                        queueW.add(new int[]{i, j});
                    }
                }
                
                B += checkArmy(queueB, "B");
                W += checkArmy(queueW, "W");
            }
        }
    
        System.out.println(W +" " + B);
    }
    
    static public int checkArmy(Queue<int[]> queue, String team) {
        int count = 0;
        while(!queue.isEmpty()) {
            int[] next = queue.poll();
            int qi = next[0]; int qj = next[1];
            count++;
        
            for(int k = 0; k<4; k++) {
                int nexti = dirI[k] + qi;
                int nextj = dirJ[k] + qj;
            
                // 상하좌우 병사 확인 
                if (nexti >= 0 && nexti < N && nextj >= 0 && nextj < M && !visited[nexti][nextj] && matrix[nexti][nextj].equals(team)) {
                    visited[nexti][nextj] = true;
                    queue.add(new int[]{nexti, nextj});
                }
            }
        }
        
        return count*count;
    }
}