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

2667

접근법

1. 지도를 돌면서 (1)집이 있고 (2)아직 방문하지 않은 집(단지)인지 체크
   • 사방 탐색 + 완전 탐색을 위한 bfs/dfs
   • 방문 체크를 위한 배열 필요
2. 그렇다면 인접한 집들에 단지 번호를 붙여줌
3. 각 단지의 수가 몇 개인지 체크 후 리스트에 추가해줌
4. 단지 수는 마지막 단지번호와 동일

+ 그래프?

계속 인접리스트/인접행렬로 그래프부터 그려야 하는 문제 풀다가 헷갈렸던 부분...
이 문제는 지도 = 모든 좌표가 인접한 사방의 좌표와 이미 연결되어 있기 때문에 굳이 그래프를 그릴 필요가 없다.
= 하나의 노드와 인접한 사방의 4개 노드는 무조건 연결되어 있으므로...

코드

• bfs 사용
• Position class 만들어서 x, y 좌표 저장해줬는데 그럴 필요 없이 정수 배열로 저장했어도 됨
• 마지막에 한번 더 탐색 돌면서 단지마다 집의 개수를 카운트해줬는데 그럴 필요 없이 bfs 돌면서 cnt++ 해주고 마지막에 list에 넣어줬어도 될듯...

package boj.silver.step1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BOJ2667 {

	static int cnt = 1;
	static int N;
	static int[][] map;
	static int[][] result;
	static boolean[][] visited;

	static int[] dx = { 1, -1, 0, 0 };
	static int[] dy = { 0, 0, 1, -1 };

	static class Pair {
		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		
		N = sc.nextInt();
		sc.nextLine();
		
		map = new int[N][N];
		result = new int[N][N];
		visited = new boolean[N][N];

		for (int i = 0; i < N; i++) {
			String temp = sc.nextLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = temp.charAt(j) - '0';
			}
		}
		

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					bfs(i, j);
					cnt++;
				}
			}
		}
		
//		System.out.println(Arrays.deepToString(result));
		
		int[] list = new int[cnt];
		
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (result[i][j] != 0)
					list[result[i][j]]++;
			}
		}
//		System.out.println(Arrays.toString(list));
		
		Arrays.sort(list);
		
		System.out.println(cnt-1);
		for (int i = 1 ; i < cnt; i++) {
			System.out.println(list[i]);	
		}
	}

	static void bfs(int x, int y) {
		Queue<Pair> queue = new LinkedList<Pair>();
		queue.add(new Pair(x, y));
		visited[x][y] = true;
		result[x][y] = cnt;

		while (!queue.isEmpty()) {
			Pair p = queue.poll();

			for (int d = 0; d < 4; d++) {
				int nx = p.x + dx[d];
				int ny = p.y + dy[d];

				if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visited[nx][ny] && map[nx][ny] == 1) {
					result[nx][ny] = cnt;
					queue.offer(new Pair(nx,ny));
					visited[nx][ny] = true;
				}

			}

		}

	}

}