문제
내가 생각했을때 문제에서 원하는부분
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v)
모든 간선의 (u, v) 쌍의 값은 서로 다르다.
첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다.
i번째 줄에는 정점 i의 깊이를 출력한다.
시작 정점 R의 깊이는 0이고 방문 되지 않는 노드의 깊이는 -1로 출력하자.내가 이 문제를 보고 생각해본 부분
변수 선언 및 초기화:
static ArrayList<ArrayList<Integer>> adj;: 그래프의 인접 리스트를 표현하는 데 사용된다.
adj.get(i)는 i번 정점에 인접한 모든 정점의 목록을 담고 있다.
무방향 그래프이므로 양쪽 정점에 모두 간선을 추가한다.
static int[] depth;: 각 정점의 깊이를 저장할 배열입니다. depth[i]는 i번 정점의 깊이를 나타낸다.
방문하지 않은 정점은 기본값인 -1로 설정된다.
static int N_nodes;: 정점의 개수를 저장하는 변수이다.
입력 처리:
BufferedReader와 StringTokenizer를 사용하여 정점의 수 N_nodes, 간선의 수 M, 시작 정점 R을 입력받는다.
adj 리스트와 depth 배열을 N_nodes + 1 크기로 초기화합니다. 배열 인덱스를 정점 번호(1부터 N)와 맞추기 위함이다.
depth 배열의 모든 원소를 -1로 초기화합니다. 이것은 '아직 방문하지 않음'을 의미한다.
M번 반복하면서 간선 정보 u v를 읽어와 adj.get(u).add(v);와 adj.get(v).add(u);를 통해 인접 리스트에 추가한다.
양방향 간선이기 때문에 두 정점 모두에 추가해야 한다.
인접 리스트 정렬:
핵심 조건인 "인접 정점은 내림차순으로 방문한다"를 만족시키기 위해 각 정점의 인접 리스트(adj.get(i))를 Collections.sort(adj.get(i), Collections.reverseOrder());를 사용하여 내림차순으로 정렬한다.
DFS는 이 정렬된 순서대로 인접 정점을 방문하게 된다.
DFS 호출:
dfs(R, 0);를 호출하여 시작 정점 R부터 깊이 우선 탐색을 시작한다.
시작 정점의 깊이는 0이다.
결과 출력:
StringBuilder를 사용하여 1번부터 N_nodes번까지의 각 정점의 depth 값을 한 줄씩 출력한다.
StringBuilder를 사용하면 많은 양의 출력을 효율적으로 처리할 수 있다.
dfs 메소드:
public static void dfs(int u, int d): 현재 탐색 중인 정점 u와 그 정점의 깊이 d를 매개변수로 받는다.
depth[u] = d;: 현재 정점 u의 깊이를 d로 기록합니다. 이 과정을 통해 정점 u가 방문되었음을 표시하게 된다.
for(int v : adj.get(u)): u에 인접한 모든 정점 v에 대해 반복한다.
이 adj.get(u) 리스트는 이미 내림차순으로 정렬되어 있다.
if(depth[v] == -1): 만약 인접한 정점 v가 아직 방문되지 않았다면 (깊이가 -1이라면),
dfs(v, d + 1);: 재귀적으로 v 정점에 대해 DFS를 호출하고, v의 깊이는 u의 깊이보다 1 증가한 d + 1이 된다.코드로 구현
package baekjoon.baekjoon_31;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
// 백준 24482번 문제
public class Main1234 {
static ArrayList<ArrayList<Integer>> adj; // 그래프의 인접 리스트
static int[] depth; // 각 정점의 깊이를 저장할 배열
static int N_nodes; // 정점의 개수 (클래스 변수명 N과 충돌을 피하기 위해 변경)
public static void dfs(int u, int d) {
// 현재 정점 u의 깊이를 d로 설정합니다.
depth[u] = d;
// 현재 정점 u와 연결된 모든 인접 정점을 순회합니다.
// 인접 리스트는 이미 내림차순으로 정렬되어 있습니다.
for (int v : adj.get(u)) {
// 만약 인접 정점 v가 아직 방문되지 않았다면 (깊이가 -1이라면)
if (depth[v] == -1) {
// v를 다음 방문할 정점으로 하여 DFS를 재귀 호출하고 깊이를 1 증가시킵니다.
dfs(v, d + 1);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N_nodes = Integer.parseInt(st.nextToken()); // 정점의 수
int M = Integer.parseInt(st.nextToken()); // 간선의 수
int R = Integer.parseInt(st.nextToken()); // 시작 정점
// 인접 리스트 초기화 (1번 정점부터 N_nodes번 정점까지 사용하므로 N_nodes + 1 크기로 만듭니다)
adj = new ArrayList<>();
for (int i = 0; i <= N_nodes; i++) {
adj.add(new ArrayList<>());
}
// 깊이 배열 초기화 (1번 정점부터 N_nodes번 정점까지 사용하므로 N_nodes + 1 크기로 만듭니다)
depth = new int[N_nodes + 1];
// 모든 정점의 깊이를 -1로 초기화합니다.
for (int i = 1; i <= N_nodes; i++) {
depth[i] = -1;
}
// M개의 간선 정보를 읽어서 인접 리스트에 추가합니다.
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
// 무방향 그래프이므로 양쪽에 모두 추가합니다.
adj.get(u).add(v);
adj.get(v).add(u);
}
// 문제 조건: 인접 정점을 내림차순으로 방문해야 합니다.
// 따라서 각 정점의 인접 리스트를 내림차순으로 정렬합니다.
for (int i = 1; i <= N_nodes; i++) {
Collections.sort(adj.get(i), Collections.reverseOrder());
}
// 시작 정점 R부터 깊이 우선 탐색을 시작합니다. R의 깊이는 0입니다.
dfs(R, 0);
// 결과 출력을 위한 StringBuilder를 사용합니다.
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= N_nodes; i++) {
sb.append(depth[i]).append("\n"); // 각 정점의 깊이를 한 줄씩 추가합니다.
}
System.out.print(sb.toString()); // 최종 결과를 출력합니다.
br.close(); // BufferedReader를 닫아 자원을 해제합니다.
}
}
마무리
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.
Junior backend developer