[백준/2667/Java] 단지번호붙이기

 

 

문제

2667번: 단지번호붙이기 (acmicpc.net)

2667번: 단지번호붙이기

 

문제를 먼저 풀고 오시는 것을 추천합니다.

이 문제의 풀이는 BFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

 

문제분석

1은 집이 있는 곳이며, 0은 집이 없는 곳을 나타냅니다.

상하좌우로 연결된 집들의 모임이 단지입니다.

각 단지에 속하는 집의 수를 센 다음 오름차순으로 정렬해야 합니다.

 

입력

첫번째 줄에 지도의 크기 N (5 <= N <= 25)가 주어집니다. 정사각형이므로 가로, 세로의 크기는 동일합니다.

그 다음 N개 줄에 각각 N개의 자료(0 또는 1)이 입력됩니다.

 

출력

첫번째 줄에 총 단지수를 출력합니다.

각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력합니다.

 

 

풀이

2차원 배열은 2개를 선언합니다.

입력값으로 받은 2차원 배열과 방문여부를 저장하는 2차원 배열입니다.

방문여부를 저장할 때 0, 1 대신 단지번호를 저장하도록 하겠습니다. 검증하기 편하게 하기 위해서입니다.

 

(0, 0)부터 (N-1, N-1)까지 집 하나씩 찾아보며 연결된 집이 있는지 BFS로 확인합니다.

BFS 할 때마다 단지수를 더하여 단지번호로 저장하고 방문여부를 저장하는 2차원 배열에 단지번호를 표시합니다.

 

연결된 집을 찾을 때마다 집수를 더합니다.

더 이상 연결된 집이 없으면 BFS를 종료하고 집의 수를 1차원 배열에 단지번호를 인덱스로 하여 저장합니다.

이렇게 반복하다가 2차원 배열 모두 찾으면 1차원 배열을 오름차순으로 정렬하여 각 단지내 집의 수를 오름차순으로 출력할 수 있습니다.

 

예제풀이

문제에 있는 예제로 어떻게 동작하는지 확인해보겠습니다.

 

초기값

입력값으로 2차원 배열을 생성하고 값을 설정하면 이렇게 됩니다.

 

 

1번째 단지

(0, 0)이 0이므로 (1, 0)에 있는 1에서부터 BFS를 시작하며, 단지번호는 1번이 됩니다. (노란색으로 표시)

연결된 집을 모두 찾으면서(주황색으로 표시) 집의 수를 셉니다. 

집의 수는 7이므로 집의 수 첫번째 인덱스에 7을 저장합니다.

 

2번째 단지

1번째 단지를 (1, 0) 위치부터 시작해서 찾았으므로 다시 오른쪽으로 이동하면서 집이 있는지 찾기 시작합니다.

(4, 0)에 있는 1에서부터 BFS를 시작하며, 단지번호는 2번이 됩니다. (노란색으로 표시)

연결된 집을 모두 찾으면서(주황색으로 표시) 집의 수를 셉니다. 

집의 수는 8이므로 집의 수 두번째 인덱스에 8을 저장합니다.

 

3번째 단지

1번째 단지를 (4, 0) 위치부터 시작해서 찾았으므로 다시 오른쪽으로 이동하면서 집이 있는지 찾기 시작합니다.

(5, 4)에 있는 1에서부터 BFS를 시작하며, 단지번호는 3번이 됩니다. (노란색으로 표시)

연결된 집을 모두 찾으면서(주황색으로 표시) 집의 수를 셉니다. 

집의 수는 9이므로 집의 수 두번째 인덱스에 9를 저장합니다.

 

 

 

소스

입력받은 값은 2차원 배열 g에 저장하였습니다.

방문정보(단지번호)는 2차원 배열 d에 저장하였습니다.

g와 d 배열은 N x N 크기를 가지고 있습니다.

집의 수를 저장하는 1차원 배열의 이름은 list로 하였습니다.

 

list 배열을 정렬할 때 0번 인덱스부터 끝까지 전체를 정렬하지 않고

1번 인덱스부터 단지번호까지만 정렬하기 위해서 Arrays.sort 함수를 사용할 때 인덱스를 지정하였습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main
{
	static int N;
	static char g[][] = new char[25][25];

	static int d[][] = new int[25][25];
	static int num;
	
	static int list[] = new int[625];
	
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.valueOf(br.readLine());

		String input = null;
		for (int i = 0; i < N; i++)
		{
			input = br.readLine();
			for (int j = 0; j < N; j++)
			{
				g[i][j] = input.charAt(j);
			}
		}
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (g[i][j] == '1' && d[i][j] == 0)
				{
					num++;
					bfs(i, j);
				}
			}
		}
		
//		System.out.println(Arrays.toString(list));
		
		Arrays.sort(list, 1, num+1);	// 1번 인덱스부터 단지수만큼 범위를 지정하여 오름차순으로 정렬
		
		System.out.println(num);
		for (int i = 1; i <= num; i++)
		{
			System.out.println(list[i]);
		}
		
		// 단지번호를 저장한 배열 출력
//		for (int i = 0; i < N; i++)
//		{
//			System.out.println(Arrays.toString(d[i]));
//		}
	}

	private static void bfs(int i, int j)
	{
		Queue<Integer> queue = new LinkedList<Integer>();
		
		queue.offer(i*100 + j);
		
		int pos = 0;
		int count = 0;
		while (queue.isEmpty() == false)
		{
			pos = queue.poll();
			i = pos / 100;
			j = pos % 100;
			
			if (d[i][j] != 0) continue;
			
			d[i][j] = num;
			count++;
			
			if (i > 0 && g[i-1][j] == '1' && d[i-1][j] == 0) queue.offer((i-1)*100 + j);	// 상
			if (i < N-1 && g[i+1][j] == '1' && d[i+1][j] == 0) queue.offer((i+1)*100 + j);	// 하
			if (j > 0 && g[i][j-1] == '1' && d[i][j-1] == 0) queue.offer(i*100 + (j-1));	// 좌
			if (j < N-1 && g[i][j+1] == '1' && d[i][j+1] == 0) queue.offer(i*100 + (j+1));	// 우
		}
		list[num] = count;
	}
}

 

관련글:

2021/02/09 - [Algorithm] - [백준/1012/Java] 유기농 배추 - BFS 풀이

[백준/1012/Java] 유기농 배추 - BFS 풀이