📌 오늘의 학습 키워드
[백준] 단지번호붙이기 (Java)
https://www.acmicpc.net/problem/2667
📌 공부한 내용 본인의 언어로 정리하기
문제 탐색하기
입력 : 첫 번째 줄 -지도의 크기 N (가로/세로 동일, 5 ≤ N ≤ 25)
N 번째 줄 - N개의 자료(0 또는 1)
출력 : 첫 번째 줄 - 총 단지수
두 번째 줄부터 - 각 단지내 집의 수를 오름차순으로 정렬해 하나씩 출력
가능한 시간복잡도
O(n^2)
n : 그리드 크기
알고리즘 선택
DFS
📌 코드 설계하기
- 격자의 크기 n을 입력받고, n개의 줄을 입력받아 각 줄을 n개의 정수로 변환하여 2차원 배열에 저장한다.
int[][] map: 입력받은 그리드를 저장할 2차원 정수 배열
boolean[][] visited: 각 위치의 방문 여부를 기록하는 불리언 배열
ArrayList complexSizes: 각 단지의 크기를 저장할 리스트 - 네 방향(상, 하, 좌, 우)을 탐색하기 위한 방향 벡터를 설정한다.
- DFS는 현재 위치에서 시작하여 연결된 모든 1을 방문하며, 단지의 크기를 센다. 상하좌우 방향으로 이동하며 아직 방문하지 않은 1을 재귀적으로 탐색한다.
- 격자의 모든 위치를 탐색하며, 방문하지 않은 1이 발견되면 새로운 단지를 발견한 것으로 간주하고 DFS를 수행한다.
- DFS 호출 후 단지의 크기를 complexSizes 리스트에 추가한다. 모든 단지의 크기를 complexSizes 리스트에 저장한 후 오름차순으로 정렬한다.
- 총 단지의 수와 각 단지의 크기를 출력합니다
📌 오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
없음
어떻게 해결했는지
없음
무엇을 새롭게 알았는지
내일 학습할 것은 무엇인지
구현
📌 정답 코드
import java.util.*;
public class Main {
static int n; // 그리드의 크기
static int[][] map; // 그리드 맵
static boolean[][] visited; // 방문 체크를 위한 배열
static int[] dx = {1, -1, 0, 0}; // x 방향 이동 (오른쪽, 왼쪽)
static int[] dy = {0, 0, 1, -1}; // y 방향 이동 (아래, 위)
static int count; // 현재 단지에 포함된 집의 수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
map = new int[n][n];
visited = new boolean[n][n];
// 그리드 입력 받기
for (int i = 0; i < n; i++) {
String line = sc.next();
for (int j = 0; j < n; j++) {
map[i][j] = line.charAt(j) - '0';
}
}
ArrayList<Integer> complexSizes = new ArrayList<>(); // 단지 크기를 저장할 리스트
// 모든 위치에 대해 DFS 실행
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && map[i][j] == 1) {
count = 0; // 새로운 단지를 탐색 시작
dfs(i, j);
complexSizes.add(count); // 탐색이 끝난 후 단지 크기 추가
}
}
}
Collections.sort(complexSizes); // 단지 크기를 오름차순으로 정렬
System.out.println(complexSizes.size()); // 총 단지 수 출력
for (int size : complexSizes) {
System.out.println(size); // 각 단지의 크기 출력
}
}
// DFS를 사용하여 단지 탐색
static void dfs(int x, int y) {
visited[x][y] = true; // 현재 위치 방문 체크
count++; // 집의 수 증가
// 네 방향 탐색
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 그리드 범위 안에 있는지 확인하고, 방문하지 않았으며 집이 있는 곳(1)인지 확인
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (!visited[nx][ny] && map[nx][ny] == 1) {
dfs(nx, ny);
}
}
}
}
}
꾸준히 정진하며 나아가기