[백준] 단계별로 풀어보기(단계:24, DFS와BFS,JAVA)2667번, 단지번호붙이기

문제 링크

2667번: 단지번호붙이기

---

주의사항

• 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배열을 통해서 맵에 해당 지점을 탐색했는지를 확인하였습니다.

문제에서 1번 단지로 표현되어 있는 곳을 DFS로 진행하는 과정을 보여드리겠습니다.(빨간색은 탐색 완료 지점)

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

 

지도의 (0,0)좌표부터 탐색을 시작하도록 하였습니다.

(0,0)은 집이 존재하지 않기 때문에 해당 지점은 탐색을 할 수 없기 때문에 넘어가겠습니다.

 

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

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

'상'

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

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

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

'하'

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

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

(1,1) 좌표는 집이 있으며 아직 탐색되지 않았기 때문에 탐색이 가능합니다.

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

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

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

(2,1)좌표에서도 (1,1)처럼 상, 하, 좌, 우로 탐색을 진행하면 상, 하는 탐색이 되지 않기 때문에 '좌'를 탐색합니다.

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

위와 같이 상, 하, 좌, 우를 반복하여 탐색하면 결과적으로 모두 탐색하기 됩니다.

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

단지가 완성되는 것을 확인할 수 있으며 탐색할 때마다 단지 내 집의 수를 더해주면서 구하면 됩니다.

결과적으로 1번 단지가 존재하며 1번 단지 내 집의 개수는 7개입니다.

 

지도의 모든 탐색을 마치면 모든 단지의 개수와 단지 내 집의 개수를 얻을 수 있습니다.

문제에서 단지 내 집의 개수를 오름차순 출력해야하기 때문에 오름차순 정렬 후 결과를 출력해야 합니다.

 

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

1. 지도의 집의 유무를 배열에 저장합니다.

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

3. 탐색을 진행하면서 단지 내 집의 수를 구합니다.

4. 탐색이 종료되면 단지 내 집의 수를 오름차순으로 정렬한 뒤 단지의 수와 단지 내 집의 개수를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• DFS을 통해 지도에 단지별 집의 개수를 구하는 dfs 함수를 만들었습니다.
• Collections.sort()를 이용하여 단지별 집의 개수를 오름차순으로 정렬하였습니다.
• BufferedWriter에 단지 개수와 단지별 집의 개수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs은 check[], dx[],dy[],map[][]과 재귀 및 리스트 result를 통해 지도를 상,하,좌,우로 탐색하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[][] map;	//지도 내 집의 유무 저장 배열
	public static int[] dx = {-1, 1, 0, 0};	//상,하,좌,우 x값 변경 배열
	public static int[] dy = {0, 0, -1, 1};	//상,하,좌,우 y값 변경 배열
	public static List<Integer> result = new ArrayList<Integer>();	//단지 내 집의 개수 저장
	public static boolean[][] check;	// 지도 내 좌표 탐색했는지 확인 배열
	public static int N;
    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
        //----------입력값 저장 및 배열 초기화-------
    	N = Integer.parseInt(br.readLine());
    	int index = 0;
    	map = new int[N][N];
    	check = new boolean[N][N];
    	for(int i=0;i<N;i++) {
    		String temp = br.readLine();
    		for(int j=0;j<N;j++) {
    			map[i][j] = Character.getNumericValue(temp.charAt(j));
    		}
    	}
        //-----지도 각 좌표를 기준으로 DFS탐색 함수 실행------
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			if(!check[i][j]) {
      				check[i][j] = true;	//해당 좌표 탐색 완료
    				if(map[i][j]==1) {	//지도 내 단지 발견
    					result.add(0);
    					dfs(i,j,index);	//함수 실행
    					index++;
    				}
    			}
    		}
    	}
    	Collections.sort(result);	//단지 내 집의 수 오름차순 정렬
    	bw.write(result.size() + "\n");	//단지 개수 BufferedWriter 저장
    	for(int i=0;i<result.size();i++) {
    		bw.write(result.get(i) + "\n");	//단지별 집의 개수 BufferedWriter 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //--------DFS를 통한 단지 내 집의 개수 탐색-----
    public static void dfs(int x, int y,int index) {
    	result.set(index, result.get(index)+1);		//단지 내 집의 개수 추가
    	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<N && !check[tempX][tempY]) {
    			check[tempX][tempY] = true;
    			if(map[tempX][tempY]==1) {
                	//지도 내에 있으며 상,하,좌,우에 인접한 집이 있을경우
    				dfs(tempX,tempY,index);		//깊이 탐색
    			}
    		}
    	}
    }
}