[BJ2667] 단지 번호 붙이기

 백준 - 단지 번호 붙이기 

문제 링크

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

2667번: 단지번호붙이기

 

문제 입출력

5
10110
01101
11011
10111
01111

3
1
7
10

 

문제 풀이

package problem.BJ;


import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class BJ2667_단지번호붙이기 {
	static int ans, cnt, N;
	static int[][] map;
	static List<Integer> cnts = new ArrayList<>();

	// 상하좌우
	static int[] dy = { 0, -1, 1, 0, 0 };
	static int[] dx = { 0, 0, 0, -1, 1 };

	static StringBuilder sb = new StringBuilder();


	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < N; j++) map[i][j] = line.charAt(j) - '0';
			// System.out.println(Arrays.toString(map[i]));
		}

		// 초기화
		cnt = 0;

		// 탐색
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				ans = 0;
				if (map[i][j] == 1) {
					dfs(i, j);
					cnt++;
					cnts.add(ans);
				}

			}

		}

		// for (int i = 0; i < N; i++) System.out.println(Arrays.toString(map[i]));

		System.out.println(cnt);
		Collections.sort(cnts);
		for (int i = 0; i < cnts.size(); i++) {
			System.out.println(cnts.get(i));
		}

	} // end main


	private static void dfs(int y, int x) {

		// 할일
		for (int d = 0; d < 5; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (map[ny][nx] == 0) continue;

			map[ny][nx] = 0; // visit 처리
			ans++;
			dfs(ny, nx);
		}

	} // end dfs
}

• 주의할 점은 오름차순으로 정렬을 해서 출력을 해야한다는 점입니다.
• dfs 를 이용하여 풀었습니다.
• visit 처리는 방문하면 map 에서 1 -> 0 으로 변경하여 visit 처리를 하였습니다.
• 단지번호를 세고나서 단지의 수를 초기화를 하여 셉니다.

 

 

 

 

 

 

 

 

 

# 단지 번호 붙이기 java # 백준 단지번호붙이기 dfs java

---