[백준]유기농 배추 - java

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

1012번: 유기농 배추

dfs 문제인데 생각보다 간단했다. 코드 실수로 인하여 시간이 오래걸렸다. 

 

실행 순서는

1. 값을 입력 받는다.

2. 좌표를 입력하면서 큐에 삽입

3. 큐에 있는 값을 하나씩 poll 하면서 dfs 탐색

4. 결과 값 출력

 

처음에는 배열을 모두 탐색했는데, 혹시나 더 효율적인 방법이 없을까하고 검색해보다가 큐를 활용한 방법을 찾게 되었다. 

출처: www.pangsblog.tistory.com/76

이 분의 블로그를 참고하여 큐를 사용해서 문제를 풀어보았다. 전부 탐색할 필요없이 배추가 있는 좌표만 dfs를 탐색하기 때문에 훨씬 효율적이었다.

 

package javaTest;
import java.util.*;

class Baechu{
	int x;
	int y;

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

public class Dfs_2 {
	static boolean visited[][];
	static int arr[][];
	static int n,m;
	static int count;
	static Queue<Baechu> qu;
	
	
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		qu = new LinkedList<>();
		int T = sc.nextInt();
		
		for(int k = 0; k < T; k++) {
			count = 0;
			n = sc.nextInt();
			m = sc.nextInt();
			int line = sc.nextInt();
			
			arr = new int[n][m];
			visited = new boolean[n][m];
			
			for(int i = 0; i<n; i++) {
				for(int j = 0; j<m; j++) {
					arr[i][j] = 0;
					visited[i][j] = false;
				}
			}
			
			for(int i = 0; i<line; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				Baechu bae = new Baechu(x,y);
				qu.add(bae);
				arr[x][y] = 1;
			}
			
			while(qu.peek() != null) {
				Baechu sample = qu.poll();
				
				if(visited[sample.x][sample.y]==false) {
					visited[sample.x][sample.y] = true;
					count++;
					dfs(sample.x,sample.y);
				}
			}
			
			System.out.println(count);
		}
	}
	
	public static void dfs(int x, int y) {
		if(x-1>=0&&visited[x-1][y] == false&&arr[x-1][y]==1) { //top
			visited[x-1][y] = true;
			dfs(x-1,y);
		}
		if(y+1<m&&visited[x][y+1] == false&&arr[x][y+1]==1) { //right
			visited[x][y+1] = true;
			dfs(x,y+1);
		}
		if(x+1<n&&visited[x+1][y] == false&&arr[x+1][y]==1) { //bottom
			visited[x+1][y] = true;
			dfs(x+1,y);
		}
		if(y-1>=0&&visited[x][y-1] == false&&arr[x][y-1]==1) { //left
			visited[x][y-1] = true;
			dfs(x,y-1);
		}
	}

}