오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.
첫 시도 > 실패
import java.io.*;
import java.util.*;
public class Main {
static int[] visited;
static int N;
//입력 받은 걸 어떻게 처리할거냐..
//1.빈 2차원 배열에다?
//2.2차원 배열인데 연결 정보에 대한 것만
//3.
//일단 방문여부를 체크하는 숫자가 필요하다.
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int M = sc.nextInt();
int R = sc.nextInt();
visited = new int[N+1];
int[][] lines = new int[M][2];
for(int i = 0 ; i < M; i++){
lines[i][0] = sc.nextInt();
lines[i][1] = sc.nextInt();
}
Arrays.sort(lines, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {//두 배열의 첫번째 요소가 똑같다면
return Integer.compare(a[0], b[0]);
} else {
return Integer.compare(a[1], b[1]);
}
}
});
dfs(lines, R);
}
public static void dfs(int[][] E, int R) { // V : 정점 집합, E : 간선 집합, R : 시작 정점
visited[R] = 1;
System.out.print(R);
//인접한 정점들을 어떻게 뽑아낼래?
for(int i = 0 ; i < N ; i++){
if(E[i][0] == R && visited[E[i][1]] == 0){//연결되어있고 아직 방문하지 않았다면
dfs(E, E[i][1]);
}
}
}
}처음에 고민은 연결된 것들을 이동하면서 접근하는 것까지는 괜찮은데 방문하지 않았던 것은 0으로 처리하는 것에서 많은 고민을 했다.
따로 어디 저장을 해서 만들어야 하나 싶은 고민을 하다가 어짜피 visited는 0이 아닌 값이냐만 따지니까 그냥 여기다 저장하는 게 메모리적으로 이득이겠다 싶어서 기존 배열을 응용해서
import java.io.*;
import java.util.*;
public class Main {
static int[] visited;
static int N;
static int cnt;
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int R = sc.nextInt();
cnt = 1;
visited = new int[N+1];
int[][] lines = new int[M][2];
for(int i = 0 ; i < M; i++){
lines[i][0] = sc.nextInt();
lines[i][1] = sc.nextInt();
}
Arrays.sort(lines, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {//두 배열의 첫번째 요소가 똑같다면
return Integer.compare(a[0], b[0]);
} else {
return Integer.compare(a[1], b[1]);
}
}
});
dfs(lines, R);
for(int i = 1 ; i < N+1; i++){
System.out.println(visited[i]);
}
}
public static void dfs(int[][] E, int R) { // V : 정점 집합, E : 간선 집합, R : 시작 정점
visited[R] = cnt;
//인접한 정점들을 어떻게 뽑아낼래?
for(int i = 0 ; i < E.length ; i++){
if(E[i][0] == R && visited[E[i][1]] == 0){//연결되어있고 아직 방문하지 않았다면
cnt++;
dfs(E, E[i][1]);
}
}
}
}로 코드를 만들고 시도!
했지만..1%대에서 시간 초과가 났다
시간초과의 이유
- scanner보다 BufferedReader 더 이득이긴하다
-> 바꿔도 안되네.. - 정렬하는데 있어서 문제가 있을 것 같다
-> 이게 문제인 듯? - 저장하는 형태가 비효율적
3가지 이유가 가장 먼저 생각이 났다.
일단 오름차순으로 정렬을 했어야 해서 정렬을 한 번 거쳐야 하는 것은 무조건 필요했다.
정답 코드
저장 방법과 정렬 모두 변경했다.
import java.io.*;
import java.util.*;
public class Main {
static int[] visited;
static int cnt;
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int R = Integer.parseInt(st.nextToken());
visited = new int[N+1];
cnt = 1;
//정점 숫자만큼 넓혀준다.
for(int i =0; i < N+1; i++) {
graph.add(new ArrayList<>());
}
//그래프에 정보 입력
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start_dot = Integer.parseInt(st.nextToken());
int end_dot = Integer.parseInt(st.nextToken());
// 1->4 && 4->1
graph.get(start_dot).add(end_dot);
graph.get(end_dot).add(start_dot);
}
// 오름차순을 위해 정렬
for(int i = 1; i < graph.size(); i++) {
Collections.sort(graph.get(i));
}
dfs(R);
for(int i = 1 ; i < N+1; i++){
System.out.println(visited[i]);
}
}
public static void dfs(int R) { // V : 정점 집합, E : 간선 집합, R : 시작 정점
visited[R] = cnt;
//인접한 정점들을 어떻게 뽑아낼래?
for(int i = 0 ; i < graph.get(R).size(); i++){
int newVertex = graph.get(R).get(i);
if(visited[newVertex] == 0){
cnt++;
dfs(newVertex);
}
}
}
}이해하기
나는 이 문제를 단순하게 2차원 배열형태로 저장을 했다.
일단 가장 쉽게 생각났고 효율성보다는 문제를 해결할 수 있는 코드를 먼저 짜보고 싶었다.
허나 정답을 찾는 과정에서 시간초과가 났고, 그 뿐만 아니라 돌렸을 때 정답이 아닐 수도 있었다.
아무튼 저장 형태로는 2차원 배열 형태가 아닌 List형태로 저장을 하는데 이 때
List<ArrayList> graph = new ArrayList<>();
또는
List<ArrayList> graph = new ArrayList<>();
같이 저장을 한다.
그 후 값을 받아 입력하는 과정에서 주의해야할 게 있다.
일단 해당 그래프는 방향을 지니는 그래프가 아닌 양방향이다. 그러므로 저장을 2번해줘야한다.
1 -> 4 를 입력 받았을 때 1->4도 하지만, 4->1도 저장을 해야한다!!
그 후 오름차순 순으로 접근을 위해 정렬을 한 번 거쳐야 하는데
이 부분이 나에게 좀 어려웠다.
// 오름차순을 위해 정렬
for(int i = 1; i < graph.size(); i++) {
Collections.sort(graph.get(i));
}정렬을 하는데 어떻게 끄집어내서 정렬을 해야하나 라는 생각이 있었다.
그런데 쉽게 접근하면 생각보다 그렇게 어렵진 않았다. 첫번째로 우린 리스트 형태에 1,2,3,4,5 인덱스 안에 그 점이 접근할 수 있는 값들을 가지고 있기 때문에 배열로 따지자면 Array[1][] =>에 든 값들 정렬하면 된다! 이를 위해
graph.get(i)를 기준으로 sort시키는 것이다.
