[BOJ] 2667. 단지번호 붙이기 S1 JAVA

---

---

문제 이해

- 정사각형 모양의 지도에서 1은 집이 있는 곳, 0은 집이 없는 곳 - 단지 = 연결된 집의 모임  단지에 번호를 붙인다. - 연결되었다는 것은 어떤 집이 상/하/좌/우로 붙어있는 경우 (대각선상은 제외) - 지도를 입력하여 단지수를 출력, 각 단지에 속하는 집의 수(오름차순) 출력

아이디어

- dfs, bfs 등의 그래프 탐색으로 단지 카운팅 - 단지 카운트와 동시에 집 개수 카운팅 - 출력

코드

import java.io.*;
import java.util.*;

public class Main {
	static class Pos {//좌표값을 나타내기 위한 클래스 
		int x, y;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int N, map[][], cnt;
	static boolean[][] isVisited;
	static Queue<Pos> houses = new LinkedList<>();//집의 위치를 넣어줄 큐
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine()); // 맵의 가로,세로
		map = new int[N][N];// 맵배열
		isVisited = new boolean[N][N];//방문체크배열
		for (int i = 0; i < N; ++i) {
			String tmp = br.readLine();
			for (int j = 0; j < N; ++j) {
				map[i][j] = tmp.charAt(j) - '0'; // 맵 값을 입력받고
				if (map[i][j] == 1) houses.offer(new Pos(i, j)); // 집의 좌표를 넣는다
			}
		}
		int houseCnt = 0; // 전체 단지 개수
		PriorityQueue<Integer> q = new PriorityQueue<>(); // 각 단지별 집개수 
		while (!houses.isEmpty()) { // 집위치 큐가 빌때까지 반복
			Pos current = houses.poll();
			if(isVisited[current.x][current.y]) continue; // 이미 방문되었으면 통과
			cnt = 1; // 단지별 집 개수
			isVisited[current.x][current.y]=true; // 방문처리
			dfs(current, houseCnt++); // 탐색
			q.offer(cnt); // 단지별 집 개수 등록-> 몇개의 단지가 있는지 모르니까 큐로했음.
		}
		System.out.println(houseCnt);
		while(!q.isEmpty()) System.out.println(q.poll());
	}

	static int[] dx = { -1, 1, 0, 0 }; // 4방탐색
	static int[] dy = { 0, 0, -1, 1 };
	static void dfs(Pos p, int houseCnt) {
		for (int d = 0; d < 4; ++d) {
			int nx = p.x + dx[d];
			int ny = p.y + dy[d]; // 범위를 벗어나지않고, 미방문이고, 맵 값이 1이면 탐색
			if(isAvailable(nx,ny)&&!isVisited[nx][ny]&&map[nx][ny]==1) {
				isVisited[nx][ny] = true;
				dfs(new Pos(nx,ny),houseCnt);
				cnt++; // 단지별 집 개수 업
			}
		}
	}

	static boolean isAvailable(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}
}

 

 

 

---

집사는개발자가되고파