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

BaekJoon 2667. 단지번호붙이기

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

 

 

 

 

 

[문제 접근]

오랜만에 다시 BFS로 풀어 봤다.

지난번과 비슷하게 푼 것 같은데 이번에는 if문 끝나고 while문을 돌려서 cnt 값이 계속 들어 갔다.

그래서 cnt가 0이 아닐 때만 list에 넣어 줬다.

while문을 if문 안에 넣어주면 if(!cnt = 0) 조건문을 따로 해줄 필요 없이 그냥 list에 cnt를 넣어주면 된다.

 

전에 BFS랑 DFS로 푼 것도 기록해놓은게 있으니 DFS 풀이 방법은 여기서 참고 !

2019/08/22 - [Algorithm/BaekJoon] - [BOJ] 2667. 단지번호붙이기

 

 

 

 

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[][] map = new int[N][N]; //아파트 단지
		boolean[][] visit = new boolean[N][N]; //방문 배열

		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(s.charAt(j)+"");
			}
		}

		int cnt = 0;
		ArrayList<Integer> list = new ArrayList<>();

		Queue<Cord> queue = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visit[i][j]) {
					queue.add(new Cord(i, j));
					cnt++;
					visit[i][j] = true;
				}

				while (!queue.isEmpty()) {
					Cord temp = queue.poll();

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

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

						if (nx >= 0 && nx < N && ny >=0 && ny < N) {
							if (map[nx][ny] == 1 && !visit[nx][ny]) {
								queue.add(new Cord(nx, ny));
								visit[nx][ny] = true;
								cnt++;
							}
						}
					}
				}
				if (cnt != 0) {
					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;
		}

	}
}