그래프 문제(bfs,dfs) #24479: 알고리즘 수업 - 깊이 우선 탐색 1 [JAVA]

https://www.acmicpc.net/problem/24479

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

 

 

---

 

 

 

 

문제 접근

 

 

 

보통 인접 행렬(2차원 배열)로 그래프를 표현했는데 이 문제는 정점의 수와 간선의 수가 많아 인접 리스트(arraylist)로 표현함. 

-> 정점의 수는 엄청 큰데 간선의 수가 엄청 작은 경우 배열 쓰면 메모리 낭비 ㅜㅜ

 

 

 

 

 

 

 

코드

 

 

 

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

public class Main {

	static List<Integer>[] list;
	static boolean[] visited;
	static int[] order;
	static int cnt;
	static int n;

	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());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken());

		order = new int[n + 1];
		visited = new boolean[n + 1];

		list = new ArrayList[n + 1];

		for (int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			list[a].add(b);
			list[b].add(a);
		}

		// 오름차순 정렬
		for (int i = 1; i <= n; i++) {
			Collections.sort(list[i]);
		}

		dfs(r);
		for (int i = 1; i <= n; i++) {
			System.out.println(order[i]);
		}

	}

	static void dfs(int v) {

		cnt++;
		order[v] = cnt;
		visited[v] = true;

		List<Integer> l = list[v];
		for (int i = 0; i < l.size(); i++) {
			int x = l.get(i);
			if (!visited[x]) {
				dfs(x);
			}
		}
	}

}