백준 1012번: 유기농 배추

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

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

1은 배추가 있다는 것을 의미하고 0은 배추가 없다는 것을 의미한다.

배추가 상하좌우 4방향 기준으로 인접해 있는것들은 배추흰지렁이가 한 마리만 있으면 된다.

 

문제에서 가로,세로 순으로 제공한다했는데 세로,가로 순으로 풀어야 맞는 것 같다..

가로 10 세로 8 주고나서 배추 위치를 9 0 이렇게 줘버리면.. 세로가 10인건데 ㅠ  헤맸잖아용

 

import java.util.Scanner;

public class Main {

	public static int T,N,M,K,ans = 0;
	public static int[][] map;
	public static boolean[][] visit;
	public static int[] dx = {0,1,0,-1};//동남서북
	public static int[] dy = {1,0,-1,0};//동남서북
	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			ans = 0;
			N = sc.nextInt(); 
			M = sc.nextInt(); 
			K = sc.nextInt();
			map = new int[N][M];
			visit = new boolean[N][M];
			
			for (int i = 0; i < K; i++) {
				int row = sc.nextInt();
				int col = sc.nextInt();
				map[row][col]=1;
			}
			
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(map[i][j]==0)
						continue;
					if(visit[i][j])
						continue;
					
					visit[i][j]=true;
					dfs(i,j);
					ans++;
				}
			}
			
			System.out.println(ans);
		}			
	}
	
	public static void dfs(int row, int col) {
				

		//방향 탐색
		for (int i = 0; i < dx.length; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			//종료조건
			//배열 범위 밖이냐?
			if(nx >= N || ny >= M || nx < 0 || ny < 0 )
				continue;
			//배추가 없냐?
			if(map[nx][ny]==0)
				continue;
			//이미 들른 곳이냐?
			if(visit[nx][ny])
				continue;
			
			visit[nx][ny]=true;
			dfs(nx,ny);
			
		}
	}

}