[java] 백준 1012번 : 유기농 배추 (bfs, dfs)

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

문제를 읽어보면 배추가 심어져 있는 덩어리가 총 몇 개냐를 구하는 문제이다.

 

계속 bfs로 문제를 풀다보니 bfs로 해결하기는 했는데, 대부분 dfs로 문제를 푸는 것 같았다. 

 

결국 덩어리가 몇 개냐를 구하는 문제이다 보니 bfs while문으로 복잡하게 돌리는 것보다 dfs 재귀함수로 간단하게 푸는 것이 코드도 깔끔하고 간편할 것이란 생각이 들었다.

 

bfs로 풀었던 내 풀이와, 참고했던 dfs 풀이를 둘 다 기록하겠다.

---

bfs 풀이

package kakao;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class cabage_bj {
	static int[][] map;
	static boolean[][] visited;
	static int TEST, M, N, K, CNT = 0;
	static int[] dix = {1, 0, -1, 0};
	static int[] diy = {0, 1, 0, -1};
	
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		TEST = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < TEST; i++) {
			st = new StringTokenizer(br.readLine());
			
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[M][N];
			visited = new boolean[M][N];
			CNT = 0;	// 정답 초기화
			
			Queue<int[]> queue = new LinkedList<int[]>();
			
			for(int j = 0; j < K; j++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				map[x][y] = 1;	// 어디에 배추가 심어져 있는지 표시한다.
				
				queue.offer(new int[]{x, y});	// 배추 심어진 경로를 큐에 넣는다.
			}
			
			for(int j = 0; j < M; j++) {
				for(int k = 0; k < N; k++) {
					visited[j][k] = false;	// 방문 여부 false로 초기화
				}
			}
			
			bfs(queue);
		}
	}
	
	public static void bfs(Queue<int[]> queue) {
		int[] cab, cab2;
		boolean flag;
		
		while(!queue.isEmpty()) {	// 양배추가 심어진 곳을 탐색
			cab = queue.poll();
			if(visited[cab[0]][cab[1]]) continue;	// 이미 방문한 곳이면 패스(큐2에서 이미 확인한 곳일 수 있기 때문)
			
			visited[cab[0]][cab[1]] = true;
			
			CNT++;
			
			Queue<int[]> q2 = new LinkedList<int[]>();	// 한 덩어리를 탐색할 두 번째 큐
			q2.offer(cab); // 양배추가 심어져 있고 방문하지 않은 위치를 넣는다.
			
			while(!q2.isEmpty()) {	// 한 덩어리를 다 탐색할 때까지 돈다.
				cab2 = q2.poll();
				
				for(int i=0; i<4; i++) {
					int newX = cab2[0] + dix[i];
					int newY = cab2[1] + diy[i];
					
					if(newX < 0 || newY < 0 || newX >= M || newY >= N) continue;
					
					if(visited[newX][newY] || map[newX][newY] == 0) continue;
					
					visited[newX][newY] = true;
					q2.offer(new int[] {newX, newY});
				}
			}
		}
		
		System.out.println(CNT);
	}
}

 

 

---

 

dfs 풀이

package kakao;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//https://www.acmicpc.net/problem/1012
/*
*  유기농 배추 - 백준
*  dfs로 풀이
*/

public class cabage_dfs {
	static int[][] map;
	static boolean[][] visited;
	static int TEST, M, N, K, CNT = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		TEST = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < TEST; i++) {
			st = new StringTokenizer(br.readLine());
			
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			map = new int[M][N];
			visited = new boolean[M][N];
			CNT = 0;
			
			for(int j = 0; j < K; j++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				map[x][y] = 1;
			}
			
			for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    if(checklocation(j,k)){
                        CNT++;
                        dfs(j, k);
                    }
                }
            }
			
			System.out.println(CNT);
		}
		
	}
	
	public static boolean checklocation(int x, int y) {
		if(x<0 || y<0 || x>=M || y>=N) return false;
		if(map[x][y] == 0 || visited[x][y] == true) return false;
		return true;
	}

	public static void dfs(int x, int y) {
		visited[x][y] = true;
		
		if(checklocation(x-1, y)) {
			dfs(x-1, y);
		}
		if(checklocation(x, y-1)) {
			dfs(x, y-1);
		}
		if(checklocation(x+1, y)) {
			dfs(x+1, y);
		}
		if(checklocation(x, y+1)) {
			dfs(x, y+1);
		}
	}
}

 

dfs 풀이가 더 짧고 깔끔한 것을 볼 수 있다.

 

백준의 불! 문제처럼 옆칸으로 번져나가는 등의 '옆'으로 이동하는 조건이 없는 문제의 경우, 

이것처럼 뭉쳐있는 덩어리의 개수를 구하는 경우에는 dfs 로 더 간편하게 풀 수 있다는 것을 깨달았다.