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

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

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

---

[풀이 방법]

+ 내 경우에는 Scanner방식으로 입력받았을 경우 시간초과가 발생했다 😢

 

1. 그래프를 입력 받은 후, 오름차순으로 방문하기 위해 연결되어 있는 인접 정점을 내림차순으로 정렬

 

빈 Stack에 출발지를 추가하고 Stack에 요소가 존재하지 않을 때까지 다음을 반복

 

2-1) 스택에서 요소를 꺼냄

    2-1-1) 이미 꺼낸 적 있는 요소라면(이미 방문했다면) 방문처리(해당 요소의 visited값 true로 변경)를 하지 않고 다음요소 꺼냄

    2-2-2) 꺼낸 적 없는 요소라면 방문처리해주고 방문순서를 1증가시켜 order에 저장

2-3) 꺼낸 요소와 연결 된 요소들 중 방문하지 않은 요소를 Stack에 추가

 

[풀이 코드_Java]

import java.util.Stack;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Collections;

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

public class Main {
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	     
		int N = Integer.parseInt(st.nextToken()), M = Integer.parseInt(st.nextToken()), R = Integer.parseInt(st.nextToken());
		
		// 그래프 구현 
		HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken()), n2 = Integer.parseInt(st.nextToken());
			
			if (graph.get(n1) == null) graph.put(n1, new ArrayList<Integer>());
			graph.get(n1).add(n2);
			
			if (graph.get(n2) == null) graph.put(n2, new ArrayList<Integer>());
			graph.get(n2).add(n1);
		}
		
		// 인접 노드 오름차순으로 방문 하기 위해 연결되어 있는 노드들을 내림차순으로 정렬 
		for (ArrayList<Integer> val: graph.values()) Collections.sort(val, Collections.reverseOrder());
		
		
		// dfs   
		boolean[] visited = new boolean[N + 1];
		int[] order = new int[N + 1];            // 방문순서 기록할 배열 선언 
		int cnt = 0;                             // 방문순서 count할 변수 선언 
		
		Stack<Integer> stack = new Stack<>();
		stack.push(R);
		
		while (!stack.empty()) {
			int n = stack.pop();
			
			if (visited[n]) continue;
			
			visited[n] = true;
			cnt++;
			order[n] = cnt;
			
			if (graph.get(n) == null) continue;
			
			for (int i = 0; i < graph.get(n).size(); i++) {
				if (!visited[graph.get(n).get(i)]) stack.push(graph.get(n).get(i));
			}
		}
		
		// 정답 출력 
		for(int i = 1; i < order.length; i++) System.out.println(order[i]);

	}

}