[백준알고리즘-JAVA]2667번 풀이(단지번호붙이기) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2667번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2667 (단지 번호 붙이기)

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그다음 NN 줄에는 각각 N개의 자료(0 혹은(0 혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지 내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

입력, 출력 예제

성공코드

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

public class Main {

	static boolean[][] check;
	static int[][] arr;
	static char[] ch;
	static int count = 0;
	
	static int node;
	static StringBuilder sb = new StringBuilder();
	static ArrayList<Integer> ar = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		node = Integer.parseInt(br.readLine());
	
		arr = new int[node+1][node+1];
		check = new boolean[node+1][node+1];
		
		for(int i = 1 ; i <= node ; i ++) {
			String str = (br.readLine());
			ch = str.toCharArray();

			for(int j = 1 ; j <= node ; j++) {
				arr[i][j] = Character.getNumericValue(ch[j-1]);
			}
		}
		
			for(int i = 1 ; i <= node ; i++) {
				for(int j = 1 ; j <= node ; j++) {
					dfs(i,j);
					if(count != 0) {
					ar.add(count);
					count = 0;}
				}
			}
			Collections.sort(ar);
			
			sb.append(ar.size() + "\n");
			
			for(int i : ar) {
				sb.append(i + "\n");
			}
			
			System.out.println(sb);
		
		}
	public static void dfs(int a, int b) {
		if(!check[a][b]) {
			check[a][b] = true;
			
			if(arr[a][b] == 1) {
				count++;
			if( a < node && b < node) {
			if(arr[a+1][b] == 1) dfs(a+1,b);
			if(arr[a-1][b] == 1) dfs(a-1,b);
			if(arr[a][b+1] == 1) dfs(a,b+1);
			if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a < node && b >= node) {
				if(arr[a+1][b] == 1) dfs(a+1,b);
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a >= node && b < node) {
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b+1] == 1) dfs(a,b+1);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}
			else return;
			}
		}
		return;
	}
}

 이번 알고리즘 단지 번호 붙이기를 풀면서 좀 더 사실 이 방법은 DFS라고 부리기보다는 BFS 방법이라고 불러야 할 거 같네요... ㅎㅎ 네이밍이 이상해 보입니다.

 

 또한 이러한 미로 형식의 문제를 처음 접해보면서 BFS를 통해서 해결해나가는 해결법을 배워볼 수 있었습니다. 지금 다시 돌아보면 미흡한 부분도 많지만, STEP을 통해 이해해보도록 하죠.

---

알고리즘 흐름도

 입력받기 -> 인접 행렬 만들기 -> DFS함수 실행하기 -> DFS를 통해서 인접한 곳까지 가면 COUNT를 세준다. -> 출력한다.

---

STEP1 입력받기 및 행렬 만들기

for(int i = 1 ; i <= node ; i ++) {
			String str = (br.readLine());
			ch = str.toCharArray();

			for(int j = 1 ; j <= node ; j++) {
				arr[i][j] = Character.getNumericValue(ch[j-1]);
			}
		}

띄어 씌기 없이 입력됨으로 char배열을 통해서 해당 값을 arr에 넣어줍니다.

크게 어려울 것 없이 입력을 받고 행렬을 만들어 주면 됩니다.

 

여기서 왜? 2차원 배열로 만드는지 의문이 드실 수 있습니다. 문제 자체를 표형식으로 준다는 의미는 대게 2차원 배열을 활용하여 풀이하는 것이 가장 효율적인 방법이라고 인지하셔야 합니다!!

---

STEP2 DFS함수 구현하기

 사실 이 문제의 핵심입니다. 1이 입력된 값이 있으면 동서남북으로 1이 있다면 인접한 요소의 개수를 세야 합니다. 이에 따라서 저는 2가지를 활용합니다. 앞서 입력받았던 arr배열과 check 배열을 활용하여 풀이해보려 합니다.

 

public static void dfs(int a, int b) {
		if(!check[a][b]) {
			check[a][b] = true;
			
			if(arr[a][b] == 1) {
				count++;
			if( a < node && b < node) {
			if(arr[a+1][b] == 1) dfs(a+1,b);
			if(arr[a-1][b] == 1) dfs(a-1,b);
			if(arr[a][b+1] == 1) dfs(a,b+1);
			if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a < node && b >= node) {
				if(arr[a+1][b] == 1) dfs(a+1,b);
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}else if( a >= node && b < node) {
				if(arr[a-1][b] == 1) dfs(a-1,b);
				if(arr[a][b+1] == 1) dfs(a,b+1);
				if(arr[a][b-1] == 1) dfs(a,b-1);
			}
			else return;
			}
		}
		return;
	}

 식이 굉장히 지저분한데, 이동 방향을 배열로 선언한다면 더욱 간결하게 하실 수 있습니다.... 이 코드의 의미는 이렇습니다.

 - 만약 방문하지 않았다면 해당 if문을 실행합니다. 

 - 그다음 해당 행렬을 방문했다고 표시를 해주고 해당 행렬 값이 1인지 확인합니다.

 - 만약에 1이 맞다면 개수를 1개 + 해줍니다.

 - 그 후 만약에 a와 b가 입력받은 node보다 작다면 (이 의미는 해당 a, b가 저희가 입력받은 행렬보다 커질 경우를 방지) 동서남북으로 찢어져서 또 한 번 dfs함수를 실행합니다. (그렇다면, 또 해당 값이 1이라면 count에 1이 + 되겠죠?)

 - 만약 a, b가 모두 작지 않고 한 개만 작다면 그 넘어가는 라인만 빼고 dfs를 실행해 주면 됩니다.

(여기서 0 이하 값을 고려하지 않은 것은 애초에 arr과 check배열의 첫 행과 열은 모두 0으로 되어있기 때문에 두 번째 if(arr [a][b]==1)에 걸리지 않고 return이 되죠.)

 

 이런 형식으로 계속 dfs를 실행해준다면, 원하는 인접한 행렬 개수 1개가 나오게 됩니다.

---

STEP 3 DFS함수를 활용하여 결과 도출하기

			for(int i = 1 ; i <= node ; i++) {
				for(int j = 1 ; j <= node ; j++) {
					dfs(i,j);
					if(count != 0) {
					ar.add(count);
					count = 0;}
				}
			}

2중 반복문을 통해 모든 행렬을 하나하나 비교해줍니다. (여기서 2중 FOR문이어서 너무 시간낭비가 심해 보이지만, 실제로 CHECK배열을 통해서 DFS가 실행되는 횟수는 제한되기 때문에 그리 큰 시간이 소요되지는 않음을 알 수 있다.)

 

한번 DFS를 마치면 COUNT가 0이 아니라면 해당 값을 ArrayList ar에 저장해준 후 count를 초기화해줍니다. 이를 모든 arr를 방문하면 ar에는 해당 값들이 나와있습니다.

 

그렇다면 이제 정렬을 해주어 출력만 해주면 끝!

---

STEP 4 출력하기

			Collections.sort(ar);
			
			sb.append(ar.size() + "\n");
			
			for(int i : ar) {
				sb.append(i + "\n");
			}
			
			System.out.println(sb);

앞서 count값들을 저장해준 ar을 sb에 저장하여 출력하면 끝! 정렬을 하는 이유는 개수가 적은 것부터 출력이 되어야 하기 때문입니다.