1012_유기농 배추 (JAVA)

1012번: 유기농 배추

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	static int T;
	static int M, N, K;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int[][] map;
	static int[][] visited;
	static int ans;
	
	static class XY{
		int x, y;
		public XY(int x, int y){
			this.x = x; this.y = y;
		}
	}
	
	public static void main (String[] args)
	{
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		
		for(int i=0; i<T; i++){
			N = sc.nextInt(); M = sc.nextInt(); K = sc.nextInt();
			map = new int[N][M]; visited = new int[N][M];
			ans = 0;
			
			for(int j=0; j<K; j++){
				int a = sc.nextInt();
				int b = sc.nextInt();
				map[a][b]=1;
			}
			
			for(int k=0; k<N; k++){
				for(int l=0; l<M; l++){
					if(map[k][l]==1 && visited[k][l]==0) BFS(k,l);
				}
			}
			System.out.println(ans);	
		}
	}
	
	public static void BFS(int a, int b){
		Queue<XY> q = new LinkedList<XY>();
		q.offer(new XY(a,b));
		visited[a][b] = 1;
		
		while(!q.isEmpty()){
			int x = q.peek().x;
			int y = q.peek().y;
			q.poll();
			
			for(int i=0; i<4; i++){
				int xx = x + dx[i];
				int yy = y + dy[i];
			
				if(xx>=0&&xx<N && yy>=0&&yy<M){
					if(map[xx][yy]==1 && visited[xx][yy]==0){
						q.offer(new XY(xx,yy));
						visited[xx][yy]=1;
					}
				}
			}	
		}
		ans++;
	}
}

 

문제 풀때마다 내 옆에 착 붙어있는 런타임에러... 너무 화난다ㅠㅠ

구현은 금방했는데 런타임에러로 한참 걸렸다ㅠㅠㅠ

 

** 런타임에러가 난 부분은 입력받은 가로M, 세로N 문제였다.  

매번 나는 (x좌표, y좌표)로 생각하는데, '배열'에서도 이를 똑같이 생각하면 문제가 발생!!  정리해보면 아래와 같다.

 

  결론은! 문제에서 가로M, 세로N을 입력받으면 - 배열[N][M]을 만들어야한다는 것!

  문제에서 나는 가로M,세로N 순서로 입력받지 않고,

  '배열'을 기준으로 세로N, 가로M을 입력받아 배열에 편하게 사용했다.

 

[문제 풀이 생각 과정]

1. 테스트케이스T가 여러개 주어진다면, 입력받는 for문 안에서 BFS함수로 넘어가 결과를 그때마다 만들어야된다.

2. 배추가 심어져있는 땅(==1)이고 방문하지 않았다면(visited[][]==0) BFS()함수에 넣어 주변을 탐색한다.

3. 탐색이 끝나면 ans++해주고 출력! 이과정을 테스트케이스T만큼 반복한다.