1. Problem 📃

[ 단지번호 붙이기 ]

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

[ 문제 ]

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

2. Input ⌨️

[ 입력 ]

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

3. Output 🖨

[ 출력 ]

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

4. Example 📚

[ 입출력 예시 ]

5. Solution 🔑

어떻게 하면 배열의 상하좌우를 살펴볼까 생각해봤다.
2차원 배열이라면 n을 기준으로

• 상 [n-1][n]
• 하 [n+1][n]
• 좌 [n][n-1]
• 우 [n][n+1]
  위와 같은 방법을 코드로 표현하기 위한데 이를 어떻게 표현할까했다.
  다른 사람의 코드를 찾아봤더니 1차원 배열 4칸 사이즈를 두 개 정의해서
  arr1 {1, -1, 0, 0} / arr2 {0, 0, 1, -1}과 같이 정의하여 기존값에서 행,열을 하나씩 바꿔주는식으로 사용한 것을 보고 참고하여 풀었다.

1. 지도(map)를 나타낼 2차원 배열 변수, 방문 여부(visited)를 나타낼 map과 같은 크기를 가질 2차원 배열 변수, 단지별 아파트 개수를 나타낼 변수(count), count의 개수를 담아줄 리스트(list)를 선언한다.

2. 땅 크기를 나타낼 변수(N)을 정의하여 N을 입력받고 map과 visited의 크기를 N행 N열로 정의하였다. 그 후 맵에 아파트 존재하는지(1) 안 하는지(0)값을 입력받아 넣어준다.

3. 맵을 탐색하면서 아파트가 있고, 방문하지 않은 곳이라면 단지가 시작하므로 count=1 값으로 시작하여 단지 탐색(Search) 메서드를 호출한다.

   [ 아파트 단지 탐색 Search 메서드 ]

   1. 해당 좌표를 매개변수로 받는다. 그 매개변수는 방문했다고 표시한다.
   2. 해당 좌표에서 상하좌우를 탐색한다. 아까 4칸이 있었으므로 4번 루프를 돌려주는데 돌 때마다 새로운 x,y를 나타낼 변수 (nx, ny)에 위에 선언한 배열을 더하여준다.
   3. 만들어진 nx, ny값이 0보다 크고 N보다 작은, 즉 지도에서 벗어나지 않고, 방문하지도 않았으며 아파트가 있으면 그 부분 또한 방문했다고 표시하고 아파트 개수를 카운트해준다. 그리고 새로 밟은 아파트에서 또 연결된 아파트를 탐색해준다.

4. 이렇게 나온 카운트 값을 리스트에 넣어주고 맵을 모두 탐색하며 위를 반복한다.

5. 리스트를 정렬해주고 리스트의 사이즈(단지 수)를 출력, 그 후 정렬된 리스트 값들을 하나씩 출력해준다.

6. Code 💻

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;
	static char[][] map;
	static int[][] visited;
	static ArrayList<Integer> list = new ArrayList<Integer>();
	static int count;
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		map = new char[N][N];
		visited = new int[N][N];
		
		for(int i=0; i<N; i++) {
			String val = br.readLine();
			map[i] = val.toCharArray();
		}
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j] == '1' && visited[i][j] == 0) {
					count = 1;
					Search(i, j);
					list.add(count);
				}
			}
		}
		
		Collections.sort(list);
		System.out.println(list.size());
		for(int v : list) {
			System.out.println(v);
		}	
	}
	
	public static void Search(int x, int y) {
		// 방문 표시
		visited[x][y] = 1;
		
		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(visited[nx][ny] == 0 && map[nx][ny] == '1') {
					visited[nx][ny] = 1;
					count++;
					Search(nx, ny);
				}
			}		  
		}
	}
}

7. Growth 🍄

배열의 상하좌우를 살피기 위해 배열 4칸을 설정해서 확인하는 방법을 알 수 있게 된 문제였다.
그 외 방향도 확인할 수 있다.