[Eric's 백준] 2667번 - 단지번호 붙이기 - Java 🍯

문제

안녕하세요! Eric 입니다

오늘 풀어볼 문제는

백준 2667번 단지번호 붙이기 입니다

이번 문제는 dfs로 풀어보도록 하죠.

 

풀이

 

우선 단지가 몇개인지 구해야하고,

각각의 단지당, 몇개의 가구로 구성되어 있는지 구해야합니다.

이번에도 저는 boolean[] graph 값으로 받아서

단지가 있는 1 로 표시되어 있는 부분은 true 값으로 graph를 그립니다.

 

그리고 graph 에서 true값을 만마면

상하좌우를 dfs를 돌면서

각각의 단지의 개수를 찾음과 동시에, 해당 graph 위치를 false로 변환시켜줍니다.

그리고 각각의 단지 개수를 count 해줄 ArrayList를 이용해서 해당값을 저장하고

이를 오름차순으로 정렬 후 출력해줍니다.

 

그러면 코드를 보시죠.

 

코드

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Collections;
	class N2667 {
	static boolean[][] graph;
	static int n, countDanji;
	static int max = 25 + 10; // 문제에서 지도의 최대 크기가 25 이므로 거기에 넉넉하게 10 을 추가해서 진행ㅜ
	static int[] dirX = {0, 0, 1, -1};
	static int[] dirY = {1, -1, 0, 0};
	/**
	* 한번 처리한 아파트를 0으로 지워주면 되므로 visited 쓸 필요가 없음
	* */
	public static void main(String[] args) throws IOException {
	// 0. 입력 및 초기화
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	graph = new boolean[max][max];
	for (int i = 1; i <= n; i++) {
	String s = br.readLine();
	for (int j = 1; j <= n; j++) {
	graph[i][j] = s.charAt(j - 1) == '1';
	}
	}
	// 1. (1,1) 부터 (n , n) 까지 돌면서 dfs
	ArrayList<Integer> countList = new ArrayList<>();
	for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
	if (graph[i][j]) {
	countDanji = 0;
	dfs(i, j);
	countList.add(countDanji);
	}
	}
	}
	// 2. 출력
	System.out.println(countList.size());
	Collections.sort(countList);
	for (int x : countList) {
	System.out.println(x);
	}
	br.close();
	}
	public static void dfs(int x, int y) {
	graph[x][y] = false;
	countDanji++;
	for (int i = 0; i < 4; i++) {
	int cx = x + dirX[i];
	int cy = y + dirY[i];
	if (graph[cx][cy]) {
	dfs(cx, cy);
	}
	}
	}
	}

view raw N2667.java hosted with ❤ by GitHub