[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)1012번, 유기농 배추

문제 링크

1012번: 유기농 배추

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

DFS(깊이 우선 탐색)은 아래 그림처럼 어떤 조건을 가지고 목표노드에 도달하기까지 자식노드를 통해 이동하며 목표노드까지 도달하는 것을 말합니다.

자식 노드에 도착하면 그 자식노드에서 조건에 만족하는 자식노드로 다시 이동하여 목표 노드로 이동합니다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

BFS(너비 우선 탐색)은 아래 그림처럼 시작 노드에 인접한 노드를 모두 탐색한 후 인접한 노드를 기준으로 다시 인접한 노드를 찾아내는 것을 반복하여 탐색합니다.

시작 노드 탐색이 끝나면 인접했던 노드를 시작 노드로 생각하고 다시 탐색합니다.

출처 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

더 자세한 내용은 아래 링크에 들어가서 확인해주시면 감사하겠습니다.

DFS

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

BFS

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

이 문제에 핵심은

1. 0은 배추가 없는 곳, 1은 배추가 있는 곳이다.

2. 배추가 있는 곳이 서로 인접한 구역이 있으면 하나의 지렁이로 가능하다.

3. 최소 지렁이의 수를 출력해야 한다.

 

저는 DFS(깊이우선탐색)을 이용하여 문제를 해결하였습니다.

땅의 각 지점을 기준으로 상, 하, 좌, 우로 탐색을 진행하여 배추가 인접한 구역을 구하였습니다.

상, 하, 좌, 우로 탐색하기 위해서

 

dx[] = {-1, 1, 0, 0}

 

dy[] = {0, 0, -1, 1}

 

두 가지 배열을 사용하여 상, 하, 좌, 우로 깊이 탐색을 진행하였습니다.

check배열을 통해서 맵에 해당 지점을 탐색했는지를 확인하였습니다.

문제에서 (0,0) ~ (2,2) 땅을 DFS로 진행하는 과정을 보여드리겠습니다.(빨간색은 탐색 완료 지점)

1(0,0)	1	0
0	1	0
0	0	0

 

(0,0)좌표를 탐색하겠습니다.

저는 상, 하, 좌, 우 순으로 깊이탐색을 진행합니다.

'상'

0 + dx[0] = 0 + (-1) = -1

0 + dy[0] = 0 + 0 =  0

지도의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

'하'

0 + dx[1] = 0 + 1 = 1

0 + dy[1] = 0 + 0 = 0

해당 지점은 배추가 존재하지 않기 때문에 탐색되지 않습니다.

'좌'

0 + dx[2] = 0 + 0 = 0

0 + dy[2] = 0 + -1 = -1

지도의 범위를 벗어나기 때문에 탐색이 되지 않습니다.

'우'

0 + dx[3] = 0 + 0 = 0

0 + dy[3] = 0 + 1 = 1

(0,1) 좌표는 배추가 존재하며 아직 탐색되지 않았기 때문에 탐색이 가능합니다.

1	1	0
0	1	0
0	0	0

(0,1)좌표에서도 (0,0)처럼 상, 하, 좌, 우로 동일하게 탐색을 진행하면 '상'은 범위에 벗어나기 때문에 '하'를 탐색합니다.

1	1	0
0	1	0
0	0	0

(0,2)좌표에서 상, 하, 좌, 우를 모두 탐색하지 못하기 때문에 탐색을 종료합니다.

구역이 완성되는 것을 확인할 수 있습니다.

구역 한 개당 지렁이 1개라고 생각하고 모든 구역을 탐색하여 지렁의 개수를 구하면 됩니다.

 

지도의 모든 탐색을 마치면 모든 구역을 구할 수 있습니다.

구역 수 = 지렁이의 최소 수

구역 수를 결과로 출력하면 됩니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 땅의 배추의 유무를 배열에 저장합니다.

2. DFS(깊이 우선 탐색)을 이용하여 상, 하, 좌, 우 순으로 탐색을 진행합니다.

3. 탐색이 종료되면 구역의 수는 지렁이의 개수이므로 구역의 수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 배추 위치를 저장하였습니다.
• DFS을 통해 배추 구역을 구하는 dfs 함수를 만들었습니다.
• BufferedWriter에 구역의 개수(최소 지렁이 수)를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs은 check[], dx[],dy[],earth[][]과 재귀를 통해 땅을 상,하,좌,우로 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int T,N,M,K,count;
	public static int[][] earth;		//땅의 배추 유무 저장 배열
	public static int[] dx = {-1, 1, 0, 0};	//상,하,좌,우 x 변화값
	public static int[] dy = {0, 0, -1, 1};	//상,하,좌,우 y 변화값
	public static boolean[][] check;	//땅 탐색 유무
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 처리 및 배열 초기화-------
    	T = Integer.parseInt(br.readLine());
    	StringTokenizer st;
    	for(int i=0;i<T;i++) {
    		count = 0;
    		st = new StringTokenizer(br.readLine()," ");
    		N = Integer.parseInt(st.nextToken());
    		M = Integer.parseInt(st.nextToken());
    		K = Integer.parseInt(st.nextToken());
    		earth = new int[N][M];
    		check = new boolean[N][M];
    		for(int j=0;j<K;j++) {
    			st = new StringTokenizer(br.readLine()," ");
    			int X = Integer.parseInt(st.nextToken());
    			int Y = Integer.parseInt(st.nextToken());
    			earth[X][Y] = 1;
    		}
           	 //------각 땅 기준 dfs 탐색-------
    		for(int j=0;j<N;j++) {
    			for(int s=0;s<M;s++) {
    				if(!check[j][s] && earth[j][s]==1) {
    					check[j][s] = true;	//해당 땅 탐색 완료
    					dfs(j,s);		//DFS 탐색
    					count++;		//구역 추가
    				}
    			}
    		}
    		bw.write(count + "\n");		//결과 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    public static void dfs(int x, int y) {
    	for(int i=0;i<4;i++) {
    		int tempX = x + dx[i];		//상,하,좌,우 x값 변경
    		int tempY = y + dy[i];		//상,하,좌,우 y값 변경
    		if(tempX>=0 && tempX<N && tempY>=0 && tempY<M && !check[tempX][tempY]) {
            		//탐색 가능한 땅일 때
    			check[tempX][tempY] = true;		//탐색 완료
    			if(earth[tempX][tempY]==1)
    				dfs(tempX,tempY);		//DFS 탐색
    		}
    	}
    	return;
    }
}