
https://www.acmicpc.net/problem/2667
문제분석
DFS/BFS 연습용 문제를 풀기 위해 이 문제를 정했다. 문제를 보면 단지를 구하는 것이다. 단지를 그래프라고 생각하고, 그래프를 전부 순회하도록 코드를 작성하면 된다. 따라서 DFS/BFS 둘 중 아무거나 선택해도 문제를 풀 수 있게 되어있다. DFS/BFS를 공부하며 배운 구조를 활용하여 문제를 해결하면 될 것이라 생각했다.
구현에서, queue에 뭘 저장해야 하나 고민했었는데, 문제에서 주어진 N의 최대값이 25인 점을 활용하여, row*25+col값을 저장하고, poll한 뒤 25로 나눈 몫과 나머지를 적용할 수 있게끔 하였다.
코드
BFS< - >DFS 바꾸기 용이하다.
BFS용 메서드 offer과 poll 대신
DFS용 메서드 push와 pop을 사용하면 완벽히 치환된다. 결과는 당연히 같게 나온다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][N];
boolean[][] visited = new boolean[N][N];
for(int i = 0; i < N; i++){
Arrays.fill(visited[i],false);
}
for(int i = 0; i < N; i++){
String temp = br.readLine();
for(int j = 0; j < N; j++){
arr[i][j] = temp.charAt(j)-'0'; // char->int를 위함. 0과 1은 UTF-16기준 1 차이 남.
}
}
ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
ArrayList<Integer> ans = new ArrayList<Integer>();
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){ // arr [i][j]부터 탐색해 나아감.
if(arr[i][j]==1 && !visited[i][j]){ // 한번도 방문 안한 곳+집이 있는 경우
//System.out.println("queue실행, 시작 row, col : "+i+", "+j);
visited[i][j]=true;
queue.offer(25*i+j);
int count = 1;
while(!queue.isEmpty()){ // 단지 탐색 시작. 4개 방향으로 탐색
int house = queue.poll();
int row = house/25;
int col = house%25;
if(row==0){ // row 만 +1 탐색
if(!visited[row+1][col]&&arr[row+1][col]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row+1)+col);
visited[row+1][col] = true;
}
}else if(row==N-1){// row 만 -1 탐색
if(!visited[row-1][col]&&arr[row-1][col]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row-1)+col);
visited[row-1][col] = true;
}
}else{ // row 만 +1 -1 탐색
if(!visited[row+1][col]&&arr[row+1][col]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row+1)+col);
visited[row+1][col] = true;
}
if(!visited[row-1][col]&&arr[row-1][col]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row-1)+col);
visited[row-1][col] = true;
}
}
if(col==0){ // col 만 +1 탐색
if(!visited[row][col+1]&&arr[row][col+1]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row)+col+1);
visited[row][col+1] = true;
}
}else if(col==N-1){ // col 만 -1 탐색
if(!visited[row][col-1]&&arr[row][col-1]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row)+col-1);
visited[row][col-1] = true;
}
}else{ // col 만 +1 -1 탐색
if(!visited[row][col+1]&&arr[row][col+1]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row)+col+1);
visited[row][col+1] = true;
}
if(!visited[row][col-1]&&arr[row][col-1]==1){// 미탐색+이어진 경우
count +=1;
queue.offer(25*(row)+col-1);
visited[row][col-1] = true;
}
}
}
ans.add(count);
}
}
}
ans.sort((a,b)->a-b);
bw.write(String.valueOf((ans.size())));
for(int i = 0; i < ans.size(); i++){
bw.newLine();
bw.write(String.valueOf(ans.get(i)));
}
bw.flush();
bw.close();
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 2457 공주님의 정원 (1) | 2025.07.16 |
|---|---|
| [JAVA] 백준 16946 벽 부수고 이동하기 4 (2) | 2025.07.15 |
| [JAVA] 백준 2322 아령 (0) | 2025.07.08 |
| [JAVA] 백준 1715 카드 정렬하기 (0) | 2025.07.08 |
| [JAVA] 백준 2569 짐정리 (1) | 2025.07.08 |