[백준] 1303 전쟁 - 전투

www.acmicpc.net/problem/1303

1303번: 전쟁 - 전투

2020-11-15

---

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

public class Main1303 {
	public static int N, M, white, blue, arr[][];
	public static int dx[] = {-1, 0, 1, 0};
	public static int dy[] = {0, -1, 0, 1};
	public static Queue<int[]> q;
	public static boolean vtd[][];
	
	public static void solve(int num) {
		int answer = 1;
		while(!q.isEmpty()) {
			int tmp[] = q.poll();
			int x = tmp[0];
			int y = tmp[1];
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
				if(!vtd[nx][ny] && arr[nx][ny] == num) {
					q.add(new int[] {nx, ny});
					vtd[nx][ny] = true;
					answer += 1;
				}
			}
			
		}
		if(num == 0) white += (answer*answer);
		else blue += (answer*answer);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		arr = new int[N][M];
		q = new LinkedList<int[]>();
		vtd = new boolean[N][M];
		white = 0;
		blue = 0;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			String str = st.nextToken();
			for(int j = 0; j < M; j++) {
				char ch = str.charAt(j);
				arr[i][j] = (ch == 'W') ? 0 : 1;
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(!vtd[i][j]) {	
					q.add(new int[] {i, j});
					vtd[i][j] = true;
					solve(arr[i][j]);
				}
			}
		}
		System.out.println(white + " " + blue);
	}
}

1. 각 병사의 색깔을 받을 때 편의상? W => 0, B => 1로 생각했다

 

2. 전체 배열을 돌면서, 체크한 적이 없는 경우 탐색을 했다.

 

3. queue에 넣고 찾으면서 체크한 적이 없으면서 같은 색깔인 경우를 카운트 했다.

 

 

---

처음 제출 했을 때, 런타임 에러가 떠서 당황했다. 배열 인덱싱이 잘못됐을리가; 하면서 문제를 다시 읽어봤는데,

입력값에 가로 N, 세로 M이라고 쓰여있었다...

 

제대로 안 보고 습관적으로 세로를 N, 가로를 M으로 잡아서 생겼던 문제였다. 문제를 꼼꼼하게 읽는 습관을 가져야겠다

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