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

BaekJoon 2667. 단지번호붙이기

* 문제의 저작권은 BOJ 및 문제를 만든 사람에게 있습니다.

 

 

 

 

 

 

[문제 접근]

 

BFS는 방문한적이 없고 좌표 값이 1이면 cnt를 세어주고 Queue에 넣어 주고 4방향을 확인하는 것을 반복하는 방법으로 풀었다.

덩어리를 세기 위해 while문이 끝나면 리스트에 cnt 값을 넣어주고 cnt는 초기화 시켜줬다.

list는 Collections.sort로 정렬해주고 리스트의 사이즈와 리스트 안의 값들을 출력한다.

 

DFS도 BFS로 푼것과 비슷하게 풀었다.

 

 

 

 

 

 

 

 

[코드]

 

<DFS>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	static int num;
	static int[][] map;
	static boolean[][] visit;
	static int[] dx = {1, 0, -1, 0 };
	static int[] dy = {0, -1, 0, 1};
	
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());
		map = new int[num][num];
		visit = new boolean[num][num];
		
		for (int i = 0; i < num; i++) {
			String s = br.readLine();
			for (int j = 0; j < num; j++) {
				map[i][j] = s.charAt(j)-'0';
			}
		}
		
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < num; j++) {
				if (map[i][j] == 1 && visit[i][j] == false) {
					int answer = dfs(i,j, 1);
					list.add(answer);
				}
			}
		}
		System.out.println(list.size());
		Collections.sort(list);
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}
	}

	static int dfs(int x, int y, int cnt) {
		visit[x][y] = true;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx >= 0 && ny >=0 && nx <num && ny<num) {
				if (map[nx][ny] == 1 && visit[nx][ny] == false) {
					cnt++;
					visit[nx][ny] = true;
					cnt = dfs(nx, ny, cnt);
				}
			}
		}
		return cnt;
	}
}

 

 

<BFS>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

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

	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		int[][] map = new int[num][num]; //아파트 크기
		boolean[][] visited = new boolean[num][num];

		for (int i = 0; i < map.length; i++) {
			String s = br.readLine();
			for (int j = 0; j < map.length; j++) {
				map[i][j] = s.charAt(j)-'0';
			}
		}
		int cnt = 0;
		ArrayList<Integer> list = new ArrayList<>();

		Queue<Cord> queue = new LinkedList<>();
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < num; j++) {
				if (map[i][j] == 1) {
					if (visited[i][j] == true) {
						continue;
					}
					queue.add(new Cord(i, j));
					visited[i][j] = true;
					while (!queue.isEmpty()) {
						Cord temp = queue.poll();
						cnt++;
						for (int k = 0; k < 4; k++) {
							int nx = temp.x + dx[k];
							int ny = temp.y + dy[k];
							if (nx>=0 && nx < num && ny >=0 && ny <num) {
								if (map[nx][ny] == 1 && visited[nx][ny] == false) {
									visited[nx][ny] = true;
									queue.add(new Cord(nx, ny));
								}
							}
						}
					}
					list.add(cnt);
					cnt = 0;
				}
			}
		}
		Collections.sort(list);
		System.out.println(list.size());
		for (int i = 0; i < list.size(); i++) {
			System.out.println(list.get(i));
		}

	}
	static class Cord{
		int x;
		int y;

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