1. 문제 설명
2. 접근 방식
KEY WORD
: BFS
2차원 배열에 값을 담는다.
번호 별로 의미가 있다. (0
= 벽, 1
= 미방문한 아파트 단지, 2
= 방문한 단지)
(1) 2차원 배열을 순회하다가 값 == 1인 것을 만나면, 해당 값을 시작으로 BFS를 돌린다.
- 현재 값의 사방을 탐색한다.
- 사방의 값 중 1인 값이 있으면 큐에 넣고, 해당 위치의 값을 2로 바꾼다.
- 큐가 빌 때 까지 (더 이상 사방 탐색을 해도 값 = 1이 안 나올 때 까지) 반복한다.
(2) 1번은 첫 조회에서 만난 아파트의 아파트 단지 전체를 한번에 보는 것이다. 따라서 1번의 반복 횟수가 곧 아파트의 개수이다.
(3) 아파트 단지를 단지내 아파트의 개수에 따라 오름차순으로 정렬한다.
3. 코드 분석
import java.io.*;
import java.util.*;
public class Main {
// 값 저장
static int [][] arr;
// 사방 탐색용
static int [] idx = new int[]{-1,0,1,0};
static int [] idy = new int[]{0,1,0,-1};
// 아파트 단지 개수용
static int cnt = 0;
public static void main(String[] args) throws IOException {
// 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> list = new ArrayList<>();
int N = Integer.parseInt(br.readLine());
arr = new int[N][N];
for(int i = 0; i < N; i++){
String s = br.readLine();
for (int j = 0; j < N; j++) {
arr[i][j] = s.charAt(j) - 48;
}
}
// 배열을 조회 했을 때, 값이 1인 값을 만나면 그 값을 기준으로 BFS 돌리기
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(arr[i][j] == 1){
cnt++;
list.add(bfs(new Coordinate(i,j)));
}
}
}
// 값들을 아파트 개수를 기준으로 오름차순 정렬
Collections.sort(list);
System.out.println(cnt);
for(int temp: list){
System.out.println(temp);
}
}
public static int bfs(Coordinate now) {
// 공터: 0, 미방문 단지: 1, 방문한 단지: 2
// 현재 탐색 중인 아파트단지의 아파트 갯수 카운트
int apart_cnt = 1;
ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
// 첫 조회한 아파트를 집어 넣기
aq1.add(now);
// 방문 표시
arr[now.x][now.y] = 2;
while(!aq1.isEmpty()) {
Coordinate cur = aq1.poll();
// 사방 탐색
for (int i = 0; i < 4; i++) {
int nx = cur.x + idx[i];
int ny = cur.y + idy[i];
// 배열 범위 안이고, 미방문한 아파트라면,
if(nx>=0 && ny>= 0 && nx< arr.length && ny < arr.length){
if(arr[nx][ny] == 1) {
// 방문처리 후에 해당 아파트를 기점으로 4방 탐색하기 위해 queue에 넣는다.
arr[nx][ny] = 2;
aq1.add(new Coordinate(nx,ny));
apart_cnt++;
}
}
}
}
return apart_cnt;
}
}
class Coordinate {
int x;
int y;
public Coordinate (int x, int y) {
this.x = x;
this.y = y;
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
99 클럽 코테 스터디 17일차 TIL + 백준 17834 사자와 토끼 완벽 설명! (0) | 2024.08.07 |
---|---|
Programmers K진법에서 소수 개수 구하기 java 쉬운 풀이^^ (0) | 2024.08.07 |
99 클럽 코테 스터티 16일차 TIL + 프로그래머스 N-queen java 쉬운 풀이! (0) | 2024.08.06 |
99 클럽 코테 스터티 15일차 TIL + 프로그래머스 소수 찾기 java (0) | 2024.08.06 |
99클럽 코테 스터디 13일차 TIL + Programmers 입국 심사대 java (0) | 2024.08.03 |