[ Baekjoon ] #2667 단지 번호 붙이기

[Baekjoon][https://www.acmicpc.net/problem/2667]

 

기본적인 DFS 그래프 문제

풀이)

  (1) 입력한 영역을 배열로 저장: map[n]

  (2) getDFS 메소드로 DFS 탐색 처리

       - visit[n][n] : 1인 구간은 탐색 완료 / 0 은 이동 가능

  (3) ←,↑,→,↓ 방향 순으로 체크하며 getDFS 내 재귀함수로 탐색 시, 연결되어 있는 단지로 파악하여

      연결 값 증가되도록 처리 (connected++)

  (4) main 메소드 내 > 호출하는 getDFS는 연결이 아닌 단지를 처음 발견 (map[n][n] == 1 && visit[n][n] == 0)

      이므로 connected 값 초기 화 및 총 단지 값(complex_cnt)을 +1 처리한다.

 

이번 알고리즘을 풀면서 다시 체크해야할 부분은 단지 정보를 입력하는 부분으로

map[n] : 1차 배열에 String ar = sc.nextLine() 으로 입력 받은 후, 

이를 toCharArray(); 메소드를 이용하여 배열로 처리되도록 처리하였다.

 

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class baekjoon_2667 {

	static int n;
	static int[][] map;
	static int[][] visit;
	static int complex_cnt = 0;
	static int connected = 0;
	static ArrayList<Integer> connected_complex; 
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		map = new int[n][n];
		visit = new int[n][n];
		connected_complex = new ArrayList<Integer>();
		
		sc.nextLine();
		
		for(int i =0;i<n;i++) {
			String ar = sc.nextLine();
			char[] visit = ar.toCharArray();
			
			for(int j=0;j<n;j++) {
				map[i][j] = (int)visit[j] - '0';
			}
		}
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j] == 1 && visit[i][j] != 1) {
					getDFS(i, j);
					
					complex_cnt++;
					connected_complex.add(connected);
					connected = 0;
				}
			}
		}
		
		System.out.println(complex_cnt);
		Collections.sort(connected_complex);
		for(int i=0;i<connected_complex.size();i++) {
			System.out.println(connected_complex.get(i));
		}
	}
	
	public static void getDFS(int x, int y)
	{
		visit[x][y] = 1;
		connected++;
		
		int[] xx = {-1, 0, 1, 0};
		int[] yy = {0, 1, 0, -1};
		
		for(int i=0;i<4;i++)
		{
			int mx = x + xx[i];
			int my = y + yy[i];
			
			if(mx >= 0 && mx < n && my >= 0 && my < n && map[mx][my] == 1 && visit[mx][my] != 1) {
				getDFS(mx, my);
			}
		}
	}
}