1. 문제
https://www.acmicpc.net/problem/2667
2. 풀이에 대한 설명
2차원 배열을 순회하면서,
(1) 1을 만난다면! 거기서 부터 해당 1의 상하좌우 중 붙어있는 1이 있는지 확인한다. (아파트 단지 내의 아파트 수 체크)
(2) 내가 금방 방문해서 확인한 1은 -1로 값을 바꾸어서 방문 처리한다.
(3) 1 search가 끝나면 해당 아파트 단지의 아파트 수를 다 센 것이다.
(4) 이때 아파트 수를 aptList라는 아파트 단지 별 아파트 수 체크하는 곳에 저장한다.
(5) 이렇게 단지 별 아파트 수를 세면 된다.
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int [] idx = {-1,0,1,0};
static int [] idy = {0,1,0,-1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> aptList = new ArrayList<>();
// 1) 값 받기
int N = Integer.parseInt(br.readLine());
int [][] apart = new int[N][N];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
apart[i][j] = Character.getNumericValue(s.charAt(j));
}
}
// 2) 2차원 배열을 순회
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int apartCnt = 0;
// 3) 순회하다가 1을 만나면 사방탐색을 통해 근처의 아파트 단지 모두 검색 (한 번 검색한 방은 -1로 값을 바꾸기)
if(apart[i][j] == 1){
ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
aq1.add(new Coordinate(i,j));
apart[i][j] = -1;
apartCnt++;
// 3-2) 사방 탐색
while (!aq1.isEmpty()){
Coordinate now = aq1.poll();
for (int k = 0; k < 4; k++) {
int nx = now.x + idx[k];
int ny = now.y + idy[k];
// 만약 사방 검색 값이 2차원 배열안에 들어가고, 그 값이 1이면
if(nx>=0 && ny>=0 && nx < N && ny < N && apart[nx][ny] == 1){
// 값 추가
aq1.add(new Coordinate(nx,ny));
apart[nx][ny] = -1;
apartCnt++;
}
}
}
// 3-3) 1을 조우 후 BFS를 다 돌았다면, 아파트 단지 하나가 끝난 것이다.
// 따라서 해당 단지의 아파트 개수를 aptList에 넣는다.
aptList.add(apartCnt);
}
}
}
// 4) 모든 아파트 단지의 아파트 수를 출력
Collections.sort(aptList);
System.out.println(aptList.size());
for(int temp : aptList){
System.out.println(temp);
}
}
}
class Coordinate {
int x;
int y;
public Coordinate(int x, int y){
this.x = x;
this.y = y;
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
💔 14889. 스타트와 링크 (0) | 2024.03.08 |
---|---|
💜 2589 보물섬 (0) | 2024.03.06 |
💜 2606 바이러스 JAVA (0) | 2024.02.29 |
💔 9663 N-Queen java (0) | 2024.01.11 |
💔5525번 IOIOI (0) | 2024.01.05 |