백준 1303 - 전쟁 - 전투

Java

1303 번 - 전쟁 - 전투

문제

접근 방법

입력 값을 2차원 문자 배열로 저장한다.

이후 (0,0) 부터 탐색을 시작하여 방문하지 않았다면 BFS 함수를 호출한다.
해당 위치에서 부터 이어져 있는 모든 같은 색의 점을 탐색하고 방문하였다고 체크한다.
이어져 있는 개수의 제곱을 리턴하여 그 위쳑을 더하여 해결한다.

코드

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

public class Main {
	static int n, m, result;
	static char[][] map;
	static boolean[][] vis;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	m = stoi(stk.nextToken()); // 가로
    	n = stoi(stk.nextToken()); // 세로

    	map = new char[n][m];
    	vis = new boolean[n][m];
    	int white = 0;
    	int blue = 0;
    	String str;
    	for(int i = 0; i < n; i++) {
    		str = br.readLine();
    		for(int j = 0; j < m; j++) {
    			map[i][j] = str.charAt(j);
    		}
    	}
		// (0,0) 부터 탐색하여 방문하지 않았으면 이어져 있는 개수(위력)를 센다.
    	for(int i = 0; i < n; i++) {
    		for(int j = 0; j < m; j++) {
    			if(!vis[i][j]) {
    				if(map[i][j] == 'W') {
    					white += BFS(i,j,'W');
    				}
    				else {
    					blue += BFS(i,j,'B');
    				}
    			}
    		}
    	}
    	System.out.println(white + " " + blue);
    	br.close();
	}

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

	static int BFS(int y, int x, int color) {
		int cnt = 1;
		int ny,nx;

		Queue<int[]> queue = new LinkedList<>();
		int[] q;

		queue.add(new int[] {y,x});
		vis[y][x] = true;

		while(!queue.isEmpty()) {
			q = queue.poll();
			y = q[0];
			x = q[1];

			for(int i = 0; i < 4; i++) {
				ny = y + dy[i];
				nx = x + dx[i];
				// 그래프 범위에 있으며, 방문하지 않았고 같은 색일 시
				if(isIn(ny,nx) && !vis[ny][nx] && color == map[ny][nx]) {
					queue.add(new int[] {ny,nx});
					vis[ny][nx] = true;
					cnt++;
				}
			}
		}

		return (int)Math.pow(cnt, 2);	// 위력(제곱)을 구한다.
	}

	// 주어진 범위 안에 있는가
    public static boolean isIn(int y, int x){
        if(y < 0 || y >= n || x < 0 || x >= m)
            return false;
        return true;
    }
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점