문제에서 주어지길, DFS를 명시했으며, N개의 정점, M개의 간선으로 구성된 무방향 그래프라고 했다.
모든 간선의 가중치는 1이다.
인접 정점은 오름차순으로 방문한다고 했다.
단, 행렬을 사용하려고 했으나 문제가 생기는 것이,
메모리 초과가 일어나게 된다.
인풋으로 정점의 수가 10만, 간선의 수가 20만으로
인접행렬의 공간복잡도가 O(N^2)이지만 리스트로 행렬을 구현했을 시
O(N+M)으로 확 줄어드는 것을 알 수 있다.
처음에 복잡도를 신경쓰지 않고 풀어보고자 했으나, 만들고 터지는 바람에
리스트까지 같이 공부하게 됐고, 이에 대해 포스팅하고자 한다.
우선 2차원 행렬을 만들고자 했던 발상을 그대로 차용해
리스트를 통해 2차원 행렬을 흉내낸다.
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();처음에 이 구조를 봤을 때 많이 당황했다.
그렇지만 앞으로 알고리즘을 하다보면 많이 보게될 것 같아서
이에 대해 익숙해지는 것이 팔자에 좋을 것 같다.
int[] checked;또한 이번 체크 배열은 boolean을 통해서 방문했는지 아닌지만을 판단하는 것이 아닌
정수가 들어올 수 있도록 만들어 방문 체크와 동시에 방문한 순서를 기억하고자 한다.
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
int vertex = N + 1;
checked = new int[vertex]; // idx 혼란 방지를 위해 1 시작
for (int i = 0; i < vertex; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
graph.get(from).add(to);
graph.get(to).add(from);
}N을 그대로 쓰는 것이 아닌 vertex로 만든 이유는
0에 베이스를 두는 것이 아닌 1에 베이스를 둬야 문제를 헷갈리지 않고
풀어나갈 수 있을 것 같다고 판단했기 때문이다.
이에 대해서는 취사선택을 하면 될 것 같다.
필자가 이해가 안 됐던 부분은 다음이다.
for (int i = 0; i < vertex; i++) {
graph.add(new ArrayList<>());
}2차원 행렬을 흉내냈으면 끝난거 아닌가? 왜 또 어레이리스트를 리스트 안에 추가한다는 걸까?
이 때문에 또 구글링도 해봤고 다음 블로그에서 발상을 얻을 수 있었다.
hi.anna님 블로그
이를 보면서 알아챈 것은 처음에 어레이리스트를 두 번 사용했던 것은 어디까지나 내가 이차원 행렬을 사용하기 위한 세팅이다.
즉, 행과 열에 대한 빈칸을 만들어 둔 것이며, 그 안에 어떤 정보를 넣을 것인지를 준비를 안 한 것이다. 즉, 어떤 행에서 어떤 정보를 꺼내올 것인지. 그런 것을 할 수가 없기 때문에 다음과 같은 for문을 돌려서 각 행에 해당하는 리스트를 만들어 각 행에 해당하는 열을 찾아내도록 한다.
이에 대해서는 밑에서 graph를 어떻게 구성하는지 그림을 그려 보이겠다.
처음에 graph.add(new ArrayList<>()를 for 문으로 생성하면
다음과 같이 만들어진다. 0행은 일부러 생략.
이후 graph.get(from).add(to);와 graph.get(to).add(from)을 사용하면 다음과 같은 행렬이 만들어진다.
마지막으로 오름차순을 위해 Collections.sort(graph.get(i))를 하게 되면 다음과 같은 행렬로 정렬이 된다.
이후 DFS 메서드를 사용해 다음과 같은 코드를 작성한다.
현재 방문한 순서를 체크하기 위한 checked 배열에 현재의 cnt를 저장하면 된다.
static void DFS(int vertex) {
checked[vertex] = cnt; // 현재 방문한 정점에 순서를 저장
for (int i = 0; i < graph.get(vertex).size(); i++) {
int newVertex = graph.get(vertex).get(i);
// 다음 갈 정점을 방문했는지에 대한 체크
if (checked[newVertex] == 0) {
cnt++;
DFS(newVertex);
}
}
}해서 완성된 코드는 다음과 같다.
package Y2025.M12.D23;
import java.io.*;
import java.util.*;
public class Main_bj24479_깊이우선탐색1 {
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); // 정점들의 정보를 기록할 그래프
static int[] checked; // 방문한 정점을 기록할 배열
static int cnt; // 방문 순서
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
int vertex = N + 1;
checked = new int[vertex]; // idx 혼란 방지를 위해 1 시작
for (int i = 0; i < vertex; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
// 무방향 -> 양쪽에 정보를 추가
graph.get(from).add(to);
graph.get(to).add(from);
}
// 오름차순 정렬
for (int i = 1; i < graph.size(); i++) {
Collections.sort(graph.get(i));
}
cnt = 1; // 시작 정점부터 카운팅
DFS(R); // 재귀를 통한 탐색 시작
for (int i = 1; i < checked.length; i++) {
sb.append(checked[i]).append("\n");
}
System.out.println(sb);
}
static void DFS(int vertex) {
checked[vertex] = cnt; // 현재 방문한 정점에 순서를 저장
for (int i = 0; i < graph.get(vertex).size(); i++) {
int newVertex = graph.get(vertex).get(i);
// 다음 갈 정점을 방문했는지에 대한 체크
if (checked[newVertex] == 0) {
cnt++;
DFS(newVertex);
}
}
}
}해당 문제를 처음 풀면서 많은 도움을 받은 블로그
내 꿈을 JAVA님의 블로그
