본문 바로가기
My Image
Algorithm/BackJoon

[BackJoon] 백준 2667 단지번호 붙이기(DFS)

by Lim-Ky 2018. 12. 4.
반응형




백준 DFS 문제

#2667 - 단지번호붙이기


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



사용한 개념

1) DFS 


저는 깊이탐색을 사용했습니다.


우선, 2차원 배열에서 0이 아닌 1인 경우에 깊이탐색을 시작하여 인접해있는 1을 모두 찾게합니다. 그 다음 다시 탐색을 이어가 0이 아닌 1인경우 다시 깊이탐색을 시작합니다. 여기서 달라지는 점은, 이미 탐색을 했다라는 표시를 하기 위해 임시 변수 값이 CNT의 값을 증가시켜 해당 값으로 매핑시켜 표시합니ㅁ다. 


따라서..


1 1 0 0 0

1 0 0 0 0

0 0 0 1 1

1 1 0 1 1

0 1 0 0 1


인 경우,


2 2 0 0 0

2 0 0 0 0

0 0 0 3 3

4 4 0 3 3

0 4 0 0 3


위와 같이 매핑되는 것입니다.


그 다음, 매핑된 2이상의 숫자들을 숫자별로 카운트 해주면 됩니다.

cnt 는 현재 단지그룹의 수라고 보시면 됩니다.

그만큼 1차원 배열을 생성해주고, 자신이 소속된 단지번호의 값을 증가시켜 자연스럽게 1차원 배열의 index가 해당 단지 번호가 되고 그안에 있는 값은 단지번호 수가 되는 것입니다.



count = new int[cnt];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(map[i][j] > 1){
					count[map[i][j]-2]++;
				}
			}
		}




그렇게 어려운 문제는 아닙니다. 다만, 처음 DFS를 접근한다면 재귀호출에 대해 익숙해질 필요가 있습니다.




static int[] goX = {-1, 0, 1, 0};
	static int[] goY = {0, 1, 0, -1};
	private static void DFS(int a, int b, int k) {
		map[a][b] = k;

		for(int i=0; i<4; i++){
			int dx = a + goX[i];
			int dy = b + goY[i];
			
			if((-1< dx && dx<n) && (-1< dy && dy<n) && map[dx][dy] == 1){
				DFS(dx, dy, k);
			}
		}
		
	}


아래는 전체소스 입니다. 궁굼하신 점은 댓글에 남겨주세요.

package BackJoon.DFS;

import java.util.Arrays;
import java.util.Scanner;

public class PostingNumber {

	static int[][] map;
	static int[] count;
	static int n = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();	
		map = new int[n][n];
		
		for(int i=0; i<n; i++){
			String str = sc.next();	
			for(int j=0; j<n; j++){
				map[i][j] = Integer.parseInt(str.charAt(j)+"");
			}
		}
		
		solution();
		
		System.out.println(cnt);
		Arrays.sort(count);
		
		for(int i=0; i<count.length; i++){
			if(count[i] != 0)
			System.out.println(count[i]);
		}
	}
	
	static int cnt = 1;
	private static void solution() {
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(map[i][j] == 1){
					DFS(i,j,++cnt);
				}
			}
		}
		
		
		count = new int[cnt];
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(map[i][j] > 1){
					count[map[i][j]-2]++;
				}
			}
		}
		
	}
	static int[] goX = {-1, 0, 1, 0};
	static int[] goY = {0, 1, 0, -1};
	private static void DFS(int a, int b, int k) {
		map[a][b] = k;

		for(int i=0; i<4; i++){
			int dx = a + goX[i];
			int dy = b + goY[i];
			
			if((-1< dx && dx<n) && (-1< dy && dy<n) && map[dx][dy] == 1){
				DFS(dx, dy, k);
			}
		}
		
	}

}







반응형

댓글