[JAVA] 백준 2667번 - 단지번호붙이기

문제

2667번: 단지번호붙이기

[ 해결순서 ]

1. 깊이우선탐색, 너비우선탐색 어떤 방식으로도 풀 수 있는 문제지만, 나는 문제를 보자마자 깊이우선탐색로 풀어야 겠다고 떠올라 이 방식으로 해결하였다.
2. 총 단지수는 하나의 깊이우선탐색이 끝날때 변수 값을 하나씩 추가하면 되며,
3. 모든 값들을 하나씩 살펴보며 방문하지 않은 것 중 집이 있는 곳을 깊이우선탐색 한다.
4. dfs 메소드는 사실 다른 유사한 깊이우선탐색의 메소드와 비슷하다.
5. 그래도 설명하자면, 입력한 x, y값을 기준으로 상하좌우의 값을 비교하여 조건에 맞는 (방문하지 않고, 집이있으면) 그 값을 기준으로 재귀처리 함.
6. 총 단지수를 출력하고, 각 단지내의 수를 오름차순으로 정렬하여 출력 (까먹고 오름차순 정렬하지 않았다가 틀렸었다)

✏️ 한줄 평

이젠 어떤 문제가 깊이우선탐색인지 구별할 정도로는 된 것 같다. 아직 심화문제는 아니라서 그럴 순 있지만, 익숙해질 때까지 풀어야겠다.

---

코드

	package July_3;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.*;
	public class Main2667_dfs {
	static int[][] apart;
	static boolean[][] visited; //아파트 단지 배열
	static int n; //n X n 배열
	static int[] dx={-1,1,0,0}; //상하
	static int[] dy={0,0,-1,1}; //좌우
	static int count = 1;
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	n = Integer.parseInt(st.nextToken());
	apart = new int[n][n];
	visited = new boolean[n][n];
	List<Integer> result = new ArrayList<>();
	//입력
	for(int i=0; i<n; i++) {
	String s = br.readLine();
	for (int j = 0; j < n; j++) {
	apart[i][j] = s.charAt(j) - '0';
	}
	}
	int total = 0;
	for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	if(!visited[i][j] && apart[i][j] == 1){
	result.add(dfs(i,j));
	//System.out.println(dfs(i,j));
	total++;
	count = 1;
	}
	}
	}
	System.out.println(total);
	Collections.sort(result);
	for (int i : result) System.out.println(i);
	}
	/*
	1. 1을 발견하면 계속 1이 있을 때까지 깊이우선탐색
	2. 더이상 방문한적 없는 1을 발견하지 못하면 종료하고 총 단지수를 +1
	*/
	private static int dfs(int x,int y){
	visited[x][y] = true;
	for(int i=0; i<4; i++){
	int nextX = dx[i] + x;
	int nextY = dy[i] + y;
	if(nextX>=0 && nextY>=0 && nextX<n && nextY<n){ //지도에 벗어나지 않고
	if(!visited[nextX][nextY] && apart[nextX][nextY] == 1){ //방문한 적이 없으면서 1인 값이라면
	visited[nextX][nextY] = true; //방문처리하고
	count++;
	dfs(nextX,nextY);
	}
	}
	}
	return count;
	}
	}

view raw BOJ2667.java hosted with ❤ by GitHub