백준 1012번 : 유기농 배추

문제 풀이

• 접근법 : BFS
  모든 원소를 순회하면서 방문하지 않은 배추를 시작점으로 BFS를 수행하여 배추 무리를 찾아나간다.

java 구현 코드

package ch08_BFS;

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 p1012 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder output = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int T = Integer.valueOf(st.nextToken());  // 테스트 케이스의 개수 T
		
		/*
		 * 배추밭 배열 값 세팅하기
		 */
		for (int t = 0; t < T; t++) {
			
			st = new StringTokenizer(br.readLine());
			int M = Integer.valueOf(st.nextToken());  // 배추밭의 가로길이 M 
			int N = Integer.valueOf(st.nextToken());  // 배추밭의 세로길이 N 
			int K = Integer.valueOf(st.nextToken());  // 배추가 심어져 있는 위치의 개수 K

			int[][] field = new int[N][M];  // 배추밭 배열
			
			for (int k = 0; k < K; k++) {
				st = new StringTokenizer(br.readLine());
				int X = Integer.valueOf(st.nextToken());  // 배추 위치의 X좌표
				int Y = Integer.valueOf(st.nextToken());  // 배추 위치의 Y좌표
				
				// field[X][Y] = 1;  // 배추가 심어져 있음을 표시
				field[Y][X] = 1;  // 배추가 심어져 있음을 표시
			}
			
			int[] dx = {1,0,-1,0};
			int[] dy = {0,1,0,-1};
			
			Queue<Spot> queue = new LinkedList<>();  // 큐 생성
			int count = 0;  // 결괏값
			
			/*
			 * 배추밭 전체 순회하면서 방문하지 않은 배추를 시작점으로 BFS 수행
			 */
			for (int n = 0; n < N; n++) {
				for (int m = 0; m < M; m++) {
					if (field[n][m] == 1) {  // 방문 안 한 배추면
						queue.add(new Spot(m, n));  // enqueue
						field[n][m] = -1;  // 방문 표시
						count++;  // 배추 무리 + 1
					}
					
					while (!queue.isEmpty()) {
						Spot dequeue = queue.remove();  // dequeue
						
						for (int d = 0; d < 4; d++) {
							int dX = dequeue.X + dx[d];
							int dY = dequeue.Y + dy[d];
							
							if (dX < 0 || dX >= M || dY < 0 || dY >= N) continue;  // 좌표의 유효성 검증
							
							// if (field[dX][dY] == 1) {  // 유효한 좌표이고, 방문하지 않은 배추라면
							if (field[dY][dX] == 1) {  // 유효한 좌표이고, 방문하지 않은 배추라면
								queue.add(new Spot(dX, dY)); // enqueue
								field[dY][dX] = -1; // 방문 표시
							}
						}
					}
				}
			}
			output.append(count).append("\n");
		}
		System.out.println(output.toString());
	}
}

class Spot {
	int X;
	int Y;
	
	Spot(int X, int Y) {
		this.X = X;
		this.Y = Y;
	}
}

문제 해결

X좌표와 Y좌표 대입 위치 혼동으로 인해 발생한 IndexOutOfBoundsException 에러

최초 코드에서 IndexOutOfBoundsException 에러가 여기저기서 계속 발생했는데, 코드를 아무리 들여다 보아도 문제의 원인을 알아낼 수가 없었다. 그래서 결국엔 다른 사람들의 코드를 찾아 보아 원인을 알아냈다.

X좌표와 Y좌표의 잘못된 대입으로 IndexOutOfBoundsException 에러가 발생했던 것이다. 의심의 여지 없이 X좌표와 Y좌표를 (X,Y) 순서대로 대입해서 코드를 작성해 나갔는데, 그러면 안 됐다... 난 바보다ㅜ 이 실수는 나만 했을까 괜히 궁금해진다.

문제에서 다음과 같은 요구사항이 주어져 있다.
배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500) 앞으로 X,Y 좌표 대입에서 헷갈리면 문제 요구사항을 자세히 들여다 보고 힌트를 얻어야 겠다. 다시는 이러한 실수를 하지 않기 위해 그림도 한 번 그려보았다. 🙃