[백준 알고리즘] 백준 2667번 단지번호붙이기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 2667번 단지번호붙이기 자바(Java)

1) 문제번호 : 2667번

 

2) 문제 출처

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

2. 문제

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

 

3. 제약사항

- 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 맨 처음 배열을 입력받을 때, 아무생각없이 sc.nextInt()를 했다가 배열 입력을 못받는 것 때문에 5분 정도 날렸다.

- 숫자가 붙어 있어서 String형으로 받아서 charAt을 통해 숫자를 떼어 저장해야 한다.

- 배열에서 1이 발견되면 단지집의 숫자는 1이 증가하고, 1을 발견할 때 마다 1씩 증가하여 ArrayList인 result에 넣어준다. 이 것을 배열 끝까지 반복.

- 그렇게 되면 ArrayList에는 단지의 수만큼 저장이 될 것이고, ArrayList의 크기는 단지의 개수가 된다.

 

7. 소스 코드

import java.util.*;

public class Main {
	static int N; // 지도의 크기
	static int[][] Map; // 2차원 배열 지도
	static int count; // 단지집의 숫자
	static int[] dr = {-1,1,0,0}; //상하좌우
	static int[] dc = {0,0,-1,1}; //상하좌우
	
	static ArrayList<Integer> result; // 단지 집의 수 저장 result.size()는 단지 수가 된다.
	
	static boolean[][] check; // 방문 체크
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 지도의 크기

		//2차원 배열 지도
		Map = new int[N][N];
		
		//방문 체크
		check = new boolean[N][N];
		
		//지도 배열 값 입력
		for(int i=0;i<N;i++) {
			String input = sc.next();
			for(int j=0;j<N;j++) {
				Map[i][j] = input.charAt(j)-'0';
			}
		}
		
		//단지집의 숫자
		count = 0;

		//단지 집의 수 결과 저장
		result = new ArrayList<>();
		
		//지도 전체 탐색
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				//현재 위치의 값이 1이고 true라면
				if(Map[i][j]==1 && !check[i][j]) {
					//맨 처음이기 때문에 count 1 증가
					count=1;
					Search(i,j);
					result.add(count);
				}
			}
		}
		
		Collections.sort(result);
		System.out.println(result.size());
		for(int c : result) System.out.println(c);
	}
	
	public static int Search(int x, int y) {
		check[x][y] = true;
		
		//4방향 확인
		for(int i=0;i<4;i++) {
			int nx = x + dr[i];
			int ny = y + dc[i];
			
			if(nx>=0 && ny>=0 && nx<N && ny<N) {
				if(Map[nx][ny]==1 && !check[nx][ny]) {
					Search(nx,ny);
					count++;
				}
			}
		}
		
		return count;
	}
}

---