[JAVA 자바] 백준 2667번 : 단지번호붙이기

▶ 문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

▶ 설명

1이 몇개씩 모여있는지 오름차순으로 출력하는 문제이다.

 

먼저, 2차 배열로 0과 1의 값을 입력 받는다.

이 2차 배열 요소를 모두 탐색하며 1인 곳에서 DFS혹은 BFS로 탐색을 이어나가고, 0인 곳은 그냥 지나가게 한다.

DFS를 (혹은 BFS) 사용할 때 다음 노드로 탐색을 이어가기 위해서는 좌,우,위,아래의 위치를 통해 배열의 범위 밖을 넘어가는 위치, 혹은 원소 값이 0일 경우는 탐색 후보로 제외하고, 값이 1인 곳만 방문한다. 

방문을 마치면 그 1이었던 값을 0으로 바꾸어서 다음 방문 탐색에 제외시키게 한다. 그리고 방문할 때마다 카운트를 세어서 단지 안의 집 개수를 내고 ArrayList 에 그 총 개수를 저장하여서 나중에 출력할 때 반환에 쓰이도록 한다.

 

사방이 방문하지 못하는 조건으로 되어있는 경우(모든 집을 방문했다는 의미이다.)  DFS 함수에서 빠져나오면서 카운트를 세어서 단지의 개수를  알아내어 출력 첫줄에 반영하도록 한다.

 

 

 

▶ 문제 풀이

🌱 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static int n, cnt;
	static int[][] graph;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		n = Integer.parseInt(br.readLine());

		graph = new int[n][n];
		ArrayList<Integer> cntVal = new ArrayList<>();

		for (int i = 0; i < graph.length; i++) {
			String row = br.readLine();
			for (int j = 0; j < row.length(); j++) {
				graph[i][j] = row.charAt(j) - '0';
			}
		}

		int result = 0;

		for (int i = 0; i < graph.length; i++) {
			for (int j = 0; j < graph[i].length; j++) {
				cnt = 0;
				if (dfs(i, j)) {
					result++;
					cntVal.add(cnt);
				}
			}

		}
		sb.append(result).append("\n");
        Collections.sort(cntVal);
        
		for (int i = 0; i < cntVal.size(); i++) {
			sb.append(cntVal.get(i)).append("\n");

		}

		System.out.println(sb);

	}

	private static boolean dfs(int row, int col) {
		if (row >= n || row < 0 || col >= n || col < 0) {
			return false;
		}
		if (graph[row][col] == 1) {
			graph[row][col] = 0;
			cnt++;

			dfs(row - 1, col);
			dfs(row, col - 1);
			dfs(row, col + 1);
			dfs(row + 1, col);

			return true;
		}

		return false;
	}

}

 

 

 

---

 

main 메소드 내부

0과1로 되어 있는 지도를 2차원 배열로 옮기는 과정이다.

한 줄씩 입력받은 문자는 띄어쓰기 없이 되어 있으므로 charAt()메소드와 '0' 이라는 char형을 이용해 정수로 변환시켜  배열의 원소로 저장시킨다.

 

 

 

총 단지 개수를 나타내는 result변수와 각 단지를 구성하는 집의 가수를 나타내기 위한 cnt 변수를 생성/초기화 시켜서,

집들이 위치한 곳 (1로 되어 있는 곳)에 dfs 함수를 호출킬 때마다 카운트로 쓰도록 한다.

dfs 함수의 인수로 1이라는 값을 가진 곳의 위치를 넣어준다.

 

 

 

문제에서 단지내 집의 수를 오름차순으로 정렬하여 출력하라고 하였으므로  ArrayList 에 저장되어 있는 집의 개수들을 출력하기 전에 오름차순 정렬한다.

 

 

---

 

dfs 함수(메소드) 내부

1,0이 있는 배열의 범위가 아닌 곳은 탐색에서 제외하기 위해 false를 반환한다.

 

 

1인 곳을 탐색하게 된다면 1에서 0으로 값을 바꿔주어 다음 탐색에서 제외되도록 하고,

방문한 횟수를 알아내기 위해 cnt 변수로 카운트를 추가한다.

그리고 주변부로 탐색을 떠넘기기 위해 좌,우,위,아래의 인덱스를 인수로 넣은 dfs 함수를 재귀 호출하여 탐색을 반복한다. 

 

 

 

 

 

▶ Log

이전의 기본적인 DFS, BFS 문제와는 다르게 뭔가 과정이 복잡한 것 같고, 직관적인 그래프가 아닌 배열 안에서의 인접한 원소끼리의 비교를 통해 구현하는 것이 색다르다고 느껴졌지만 DFS, BFS의 기본 성질이나 특징만 잘 알고 있어도 넘어갈 만한 문제였다.