글 읽기 - JAVA] 어디에서 예외가 발생하는 것인지 모르겠습니다.

fhskf94kr 5년 전 0

채점을 해보면 50% 정도에서 틀렸습니다. 라고 나오는 것을 확인 할 수 있었습니다.

다양한 반례를 찾아보고 입력해 보았을 때, 제대로 값이 출력하는데 어느 부분에서 예외가 발생할 수 있는지 모르겠어서 질문 남깁니다.

첫 2중 for문은 방문을 확인하는 visit 배열, 배추가 있음을 표시하는 grd 배열을 초기화 시킵니다.

다음 for문을 통해 배추의 위치를 입력받아 grd에 true를, 큐에는 plants 클래스를 사용하여 x,y좌표 값을 저장합니다.

while문은 큐가 빌 때 까지 반복되며, while문 안에서는 큐를 하나씩 제거하면서 값을 찾습니다.

방문하지 않은 경우에만 if문에 들어가도록 구현했으며, 상하좌우에 방문한 흔적이 있으면 count를 줄이도록 구현했습니다.

하나의 배추 집단에는 한 마리의 지렁이만 존재하면 되기 때문에, 인접한 부분에 방문한 흔적이 있으면 그 곳에는 이미 배추가 존재하고, 지렁이도 한마리 존재하므로 방문 흔적이 있으면 count를 줄여 하나의 집단에 한마리의 지렁이만 존재하도록 구현했습니다.

어느 부분에 코드에 오류가 있는지, 어느 부분에서 예외가 발생하는지 손으로 써보면서 해봐도 못찾겠습니다..

어느 부분인지 알려주시면 감사하겠습니다.

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Problem_1012 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner scn = new Scanner(System.in);
		
		int T = scn.nextInt(); // 테스트 케이스의 갯수
		
		for(int TC = 0 ; TC < T ; TC++) {
			
			
			int M = scn.nextInt(); // 배추밭의 가로 길이
			int N = scn.nextInt(); // 배추밭의 세로 길이
			int K = scn.nextInt(); // 배추가 심어져 있는 위치의 갯수

			boolean[][] grd = new boolean[N][M];
			boolean[][] visit = new boolean[N][M];
			
			Queue<plants> q = new LinkedList<plants>();
			
			int count = 0;
			
			for(int i = 0 ; i < N ; i++) {
				for(int j = 0 ; j < M ; j++) {
					grd[i][j] = false;
					visit[i][j] = false;
				}
			}
			
			for(int i = 0 ; i < K ; i++) {
				int x = scn.nextInt();
				int y = scn.nextInt();
				grd[y][x] = true;
				q.add(new plants(x,y));
			}
			
			// q에 들어가는 데이터는 배추가 심어져 있는 위치.
			while(!q.isEmpty()) {
				plants pts = q.poll();
				int x = pts.x;
				int y = pts.y;
				int tmpC = 0;
				
				// 방문하지 않았던 곳만 확인.
				if(!visit[y][x]) {
					// 방문 표시
					visit[y][x] = true;
					// 지렁이 숫자 증가
					count++;
					
					int[] calX = { -1, 1, 0, 0 };
					int[] calY = { 0, 0, -1, 1 };
					
					// 상하 좌우 확인
					for(int i = 0 ; i < 4 ; i++) {
						int tmpX = x + calX[i];
						int tmpY = y + calY[i];
						
						// index 범위 안에 있을 경우에만 수행
						if(tmpX >= 0 && tmpY >= 0 && tmpX < M && tmpY < N) {
							// 상하좌우에 방문한적이 있으면. 
							if(visit[tmpY][tmpX] == true)
								tmpC++;
						}
					}
					// 상하좌우에 방문한 흔적이 있으면, 그 덩어리에 포함되어야 하므로 count 감소
					if(tmpC != 0) 
						count--;			
					
				}
			}
			
			System.out.println(count);
		}		
	}
}

class plants {
	int x;
	int y;
	
	public plants(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

djm03178 5년 전 1

반례입니다.

fhskf94kr 5년 전 0

감사합니다.

입력된 순서에 따라서 다르게 출력될 수 있다는 사실을 간과했었네요.

댓글을 작성하려면 로그인해야 합니다.