[1일 1알고리즘] 백준 1303. 전쟁 - 전투

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

1303번: 전쟁 - 전투

이전에 틀린문제였어서 다시 풀기로함.

지문을 읽고 2차원배열을 활용해 bfs를 구현하면 되겠다고 생각함.

코드 작성전 구현을 아래와 같이 계획했다.

boolean 2차배열 전역변수 used
char 2차배열 전역변수 field
입력받기
for( M 길이만큼 반복 )
 for( N 길이만큼 반복 )
   if ( used[m][n] 이 false면)
	 if( used[m][n] 이 'W'면)
		sumW <- bfs(m위치, n 위치)
	 if( used[m][n] 이 'B'면)
		sumB <- bfs(m위치, n 위치)
		
sumW sumB 순서대로 출력

bfs(int m, int n){
 	int형 배열 큐 초기화
	m,n 값 큐에 추가
	used[m][n] <- true
	
	int cnt = 1;
	while(큐가 비어있지 않을때까지){
		size <- 큐의 크기
		for(0이상 size값 미만 만큼 반복){
			큐에 들어있는 값 꺼내서 tmp 배열에 저장
			for(0부터 델타배열크기 미만만큼){
			 nm <- tmp[0] + dm[i]
			 nn <- tmp[1] + dn[i]
			 if(배열을 벗어나지않고 방문을 한적이 없고 큐값이랑 같으면){
				큐에 nm , nn 추가
				cnt 1 증가
			 }
			}
		}
	}
	
	return cnt*cnt;

}

해당 순서도를 바탕으로 코딩중 N과 M도 static 변수로 하는 것이 배열 크기 적용시에 좋겠다고 생각함.

결과는 값이 안나옴 -> 델타배열을 활용하여 bfs 순회시 used[nm][nn] 값을 true로 바꿔주는 것을 빼먹었다. 

 

used[nm][nn] = true 코드 추가하고 예제가 맞아서 제출했는데 18%즘에서 (ArrayIndexOutOfBounds) 발생.

확인해보니 N과 M의 위치를 바꿔서 코드를 작성함...(쩝) 

지문을 제대로 읽지 않은 나의 탓  (가로가 열이고 세로가 행이다. 헷갈리지 말자 ㅠ) 

 

결론은, 계획전 문제지문을 정확히 읽고 계획할 때는 로직에 틈이 없는지 꼼꼼히 생각할 것.

 

정답코드는 아래와 같다(문제를 아직 못푼분들은 가급적 보지 말고 위의 내용으로 힌트만 얻으시길)

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

public class Main1303 {
	static char[][] field;
	static boolean[][] used;
	static int N, M;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sizes = br.readLine().split(" ");
		N = Integer.parseInt(sizes[0]);
		M = Integer.parseInt(sizes[1]);
		field = new char[M][N];
		used = new boolean[M][N];
		for (int i = 0; i < M; i++)
			field[i] = br.readLine().toCharArray(); // 입력완료
		int sumW = 0, sumB = 0;
		for (int m = 0; m < M; m++) {
			for (int n = 0; n < N; n++) {
				if (!used[m][n]) {
					if (field[m][n] == 'W')
						sumW += bfs(m, n);
					if (field[m][n] == 'B')
						sumB += bfs(m, n);
				}
			}
		}
		System.out.println(sumW + " " + sumB);
	}

	static int[] dm = { -1, 0, 1, 0 };
	static int[] dn = { 0, 1, 0, -1 };

	private static int bfs(int m, int n) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { m, n });
		used[m][n] = true;
		char val = field[m][n];

		int cnt = 1;
		while (!q.isEmpty()) {
			int[] tmp = q.poll();
			int nown = tmp[0];
			int nowm = tmp[1];
			for (int d = 0; d < 4; d++) {
				int nm = nown + dm[d];
				int nn = nowm + dn[d];
				if (nn >= 0 && nn < N && nm >= 0 && nm < M && !used[nm][nn]) {
					if (val == field[nm][nn]) {
						q.add(new int[] { nm, nn });
						used[nm][nn] = true;
						cnt++;
					}
				}
			}
		}
		return cnt * cnt;
	}

}