[Java] 백준 1303번. 전쟁-전투 (실버1)

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

1303번: 전쟁 - 전투

 

어... 정신을 차리니 마지막 PS로부터 3주 가량이 지났습니다.

추석연휴가 껴 있기도 했고, 개인적인 일로 지방을 오가느라 시간이 없기도 했고.... 무엇보다 근무도 바빴고... 여러 사정이 있었지만 결국엔 제가 게을렀던 거겠죠.

 

Java를 하도 안쓰다 보니 (현재 하고 있는 업무에서 90% 이상 Python을 씁니다.) 다 까먹어가고 있는 느낌이라 급하게 쉬운 문제를 하나 풀어봤습니다.

 

정말 기본적인 bfs 문제라 딱히 설명할건 없네요. visit 체크만 잘해주면 풀리는 문제였습니다. 주의 할 점은 N과 M이 거꾸로 주어진다는 정도입니다. 예제에서 티가 안나는 부분이라(예제 입력에선 N == M입니다.) 첫 제출에서 index 범위가 넘어가는 런타임 에러를 당했네요. 

 

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 q1303_BOJ_전쟁전투 {
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());

		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int B = 0;
		int W = 0;

		int[][] map = new int[N][M];
		Queue<int[]> queue = new LinkedList<int[]>();

		for (int n = 0; n < N; n++) {
			char[] line = br.readLine().toCharArray();
			for (int m = 0; m < M; m++) {
				map[n][m] = (line[m] == 'W') ? 0 : 1;
			}
		}

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == 0 || map[n][m] == 1) {
					int target = map[n][m];
					int count = 0;
					queue.offer(new int[] { n, m });
					map[n][m] = -1;

					while (!queue.isEmpty()) {
						int[] now = queue.poll();
						count += 1;

						for (int i = 0; i < 4; i++) {
							int nx = now[0] + delta[i][0];
							int ny = now[1] + delta[i][1];

							if (isIn(nx, ny, N, M) && map[nx][ny] == target) {
								queue.offer(new int[] { nx, ny });
								map[nx][ny] = -1;
							}
						}

					}

					if (target == 0) {
						W += (count * count);
					} else {
						B += (count * count);
					}
				}
			}
		}

		sb.append(W).append(" ").append(B);

		System.out.println(sb);
	}

	private static boolean isIn(int x, int y, int n, int m) {
		return 0 <= x && x < n && 0 <= y && y < m;
	}
}