[백준]24479 : 알고리즘 수업 - 깊이 우선 탐색 1

문제 출처 : https://www.acmicpc.net/problem/24479

소요 시간 : 시도(30m) + 풀이

---

문제

---

시도

 

오랜만에 '데이터 구조' 전공 수업에서 듣던 알고리즘을 접했다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    private static int N, M, R;
    private static int[] visited;
    private static int[][] E;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());    // 5 ~ 100,000
        M = Integer.parseInt(st.nextToken());    // 1 ~ 200,000
        R = Integer.parseInt(st.nextToken());    // 1 ~ N
        
        visited = new int[N + 1];
        E = new int[N+1][N+1];
        
        int u, v;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            
            E[u][v] = 1;
            E[v][u] = 1;
        }
        
        dfs(R, 1);
        
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(visited[i]).append("\n");
        }
        
        System.out.print(sb);
    }
    
    private static void dfs(int R, int idx) {
        visited[R] = idx;
        
        for (int i = 1; i <= N; i++) {
            if (R != i && E[R][i] == 0) dfs(i, idx+1);
        }
    }
}

 

양방향 그래프를 구현하기 위해 2차원 int 배열 E를 정의했지만 크기 N이 100,000일 경우, 공간 복잡도가 10,000,000,000( O(N^2) )이기 때문에 메모리 초과로 실패했다.

 

결국 다른 글을 참조하여 이중 ArrayList를 활용하여 양방향 그래프를 구현했다.(링크)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.ArrayList;

public class Main {

    private static int N, M, R;
    private static int[] visited;
    private static ArrayList<ArrayList<Integer>> E;
    private static int idx = 1;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());    // 5 ~ 100,000
        M = Integer.parseInt(st.nextToken());    // 1 ~ 200,000
        R = Integer.parseInt(st.nextToken());    // 1 ~ N

        visited = new int[N + 1];
        E = new ArrayList<>();
        for (int i = 0; i <= N; i++) E.add(new ArrayList<>());

        int u, v;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());

            E.get(u).add(v);
            E.get(v).add(u);
        }

        for (int i = 1; i <= N; i++) {
            Collections.sort(E.get(i));
        }

        dfs(R);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            sb.append(visited[i]).append("\n");
        }

        System.out.print(sb);
    }

    private static void dfs(int R) {
        visited[R] = idx++;

        for(int v : E.get(R)) {
            if (visited[v] == 0) dfs(v);
        }
    }
}

 

하지만 이렇게 구현해놓고 또 문제였던 것이 간선 M의 조합이 오름차순으로 순순히 주어지는 것이 아니라 무작위로 주어질 수도 있기 때문에 결국 간선 집합 E 요소들의 각 집합에 대한 정렬을 추가로 시행해야 했다.

 

방법 i. Collections.sort()  |  방법 ii. List.sort(Comparator.naturalOrder())  |  방법 iii. Comparable 인터페이스 구현

 

방법 i을 사용하여 최종 구현했고, 1096 ms로 성공했다.

 

---

풀이

 

더 좋은 풀이를 위해 다른 사람의 풀이를 참조했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	static int n,cnt;
	static int[] visit;
	static ArrayList<Integer>[] edges;
	
	static void setList() {
		edges = new ArrayList[n + 1];
		for(int i = 1; i <= n; i++) {
			edges[i] = new ArrayList<Integer>();
		}
	}
	
	static void sorts() {
		for(int i = 1; i <= n; i++) {
			Collections.sort(edges[i]);
		}
	}
	
	static void init(int a, int b) {
		edges[a].add(b);
		edges[b].add(a);
	}
	
	static void dfs(int node) {
		if(visit[node] != 0) return;
		visit[node] = ++cnt;
		for(int i : edges[node]) {
			if(visit[i] == 0) {
				dfs(i);
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine()," ");
		StringBuilder sb = new StringBuilder();
		
		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());
		
		visit = new int[n + 1];
		
		setList();
		
		while(m-- > 0) {
			st = new StringTokenizer(in.readLine()," ");
			init(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
		}
		
		in.close();
		
		sorts();
		
		dfs(r);
		
		for(int i = 1; i <= n; i++) {
			sb.append(visit[i]).append('\n');
		}
		
		System.out.print(sb);
		
	}

}

 

커스텀된 input을 구현하지 않는 선에서 가장 빠른 코드를 참고해 적용하니 872 ms가 나왔다.

 

참고 출처 : https://www.acmicpc.net/source/66326698

---

알게 된 점

 

시도 코드와 풀이 코드 간의 시간상 성능이 200 ms 차이가 나는 이유를 고민해봤다.

코드 로직은 유사하기에 비교할 것이 없었고 결국 양방향 그래프를 정의한 방식에서 유의미한 차이가 발생했다고 가정하고 그 의미를 분석했다.

 

시도 코드는 ArrayList<ArrayList<Integer>>, 풀이 코드는 ArrayList<Integer>[]로  모두 배열과 리시트를 조합한 자료구조지만 사용 목적과 특징에 차이가 있다.

 

1. ArrayList<ArrayList<Integer>> :각 ArrayList의 크기가 동적으로  조절되기에 크기가 서로 다른 2차원 동적 배열

// ArrayList<ArrayList<Integer>> 사용 예시
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
list.add(new ArrayList<>(Arrays.asList(1, 2, 3)));
list.add(new ArrayList<>(Arrays.asList(4, 5)));
list.add(new ArrayList<>(Arrays.asList(6, 7, 8, 9)));

 

2. ArrayList<Integer>[] : 배열의 각 요소는 ArrayList 객체이며, 각각의 ArrayList는 정적 배열이므로 크기가 불변함

// ArrayList<Integer>[] 사용 예시
int size = 3;
ArrayList<Integer>[] array = new ArrayList[size];
array[0] = new ArrayList<>(Arrays.asList(1, 2, 3));
array[1] = new ArrayList<>(Arrays.asList(4, 5));
array[2] = new ArrayList<>(Arrays.asList(6, 7, 8, 9));