728x90
반응형
📜 문제 내용
🤔 과정
- 델타(dr, dc)를 통해 상, 하, 좌, 우를 탐색하면서 DFS를 활용한다.
- 방문배열 visit과 입력된 map 탐색을 하다가 1을 만나면 DFS 를 진행하고, 진행하면서 단지 수 세기
- 주변에 1이 더이상 없다면 DFS를 멈추고 해당 단지 수를 list에 추가
- 그리고 다시 visit 배열과 map 배열 탐색 반복
✨ 최초 제출 답안
import java.util.*;
import java.io.*;
public class Main {
public static int N, cnt;
public static String[][] map;
public static boolean[][] visit;
public static int[] dr = { 0, 0, -1, 1 };
public static int[] dc = { -1, 1, 0, 0 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine()); // 지도의 한 변
map = new String[N][N]; // 지도 생성
visit = new boolean[N][N]; // 방문 배열 생성
for (int i = 0; i < N; i++) {
String str = br.readLine();
map[i] = str.split(""); // 띄어쓰기가 없으므로 split으로 입력
} // 입력 끝
List<Integer> list = new ArrayList<>(); // 단지가 담길 리스트 생성
for (int i = 0; i < N; i++) { // 행
for (int j = 0; j < N; j++) { // 열
cnt = 0; // 한 단지 내 가구 수
// 방문하지 않았고, 아파트가 있다면
if (!visit[i][j] && map[i][j].equals("1")) {
DFS(i, j); // 깊이 우선 탐색(행,열)
list.add(cnt); // 단지 내 가구 수를 리스트에 입력
}
}
}
Collections.sort(list); // 리스트 오름차순 정렬
sb.append(list.size()).append("\n"); // 리스트 사이즈가 곧 총 단지 수
for (int cnt : list) { // 한 단지 내 가구 수 출력
sb.append(cnt).append("\n");
}
br.close();
bw.append(sb);
bw.flush();
bw.close();
}// main
public static void DFS(int r, int c) { // r은 행, c는 열
visit[r][c] = true; // 방문 한 곳을 표시
cnt++; // 한 가구수 표시
for (int i = 0; i < 4; i++) {
int nr = r + dr[i]; // 델타로 위치 갱신 , 행
int nc = c + dc[i]; // 델타로 위치 갱신 , 열
// 경계 안에 있고, 방문하지 않았고, 아파트가 있다면
if (nr >= 0 && nr < N && nc >= 0 && nc < N
&& !visit[nr][nc] && map[nr][nc].equals("1")) {
// 다시 DFS 재귀
DFS(nr, nc);
}
}
}
}
- 탐색을 진행하면서 경계 확인하는 과정을 따로 메서드로 만들어 빼내어도 깔끔해질 것 같다.
🔗 문제 링크
728x90
반응형
