문제 내용은 입력으로 정점, 간선, 시작 정점을 받은 뒤 그래프를 만들고 시작 정점부터 탐색하기 시작했을 경우 1부터 N까지의 정점의 방문 시점을 출력해주면 되는데 먼저 방문한 순서대로 출력이 아니라, 2번이 처음, 1번이 그 다음이면 2, 1.. 이런 식으로 출력해줘야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class Main {
static int[] visited;
static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
static int incre = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] vertexEdgesStart = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
.toArray();
for (int i = 0; i < vertexEdgesStart[1]; i++) {
int[] edge = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
graph.putIfAbsent(edge[0], new ArrayList<>());
graph.putIfAbsent(edge[1], new ArrayList<>());
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
visited = new int[vertexEdgesStart[0] + 1];
for (ArrayList<Integer> arr : graph.values()) {
arr.sort(Collections.reverseOrder());
}
dfs(vertexEdgesStart[2]);
for (int i = 1; i < visited.length; i++) {
System.out.println(visited[i]);
}
}
public static void dfs(int start) {
visited[start] = incre;
if (graph.get(start) != null) {
for (Integer i : graph.get(start)) {
if (visited[i] == 0) {
incre += 1;
dfs(i);
}
}
}
}
}문제를 풀어보자면 먼저 간선에 맞게 양방향 그래프를 만들어준 뒤, 정점별 간선을 모두 내림차순 정렬해준 다음, int[] 배열을 정점 갯수보다 +1 해서 만들고(정점은 1부터 시작하니), 시작 정점부터 그래프를 탐색하기 시작하면서 visited 배열에 방문 순서대로 1부터 올려가며 찍어준 뒤, 그래프 탐색을 마치고 나면, 1부터 N까지 정점 방문 순서를 찍어주면 끝이다.
Leave a Reply