문제 내용은 이전 문제인 알고리즘 수업 – 너비 우선 탐색 1과 하나만 빼면 동일한데, 인접 정점을 내림차순으로 방문한 뒤, 값별 방문 순서를 출력해주면 된다.
이전 문제를 풀지 않았다면 주의할 점은, 출력 시, 방문한 값 순서가 아니라, 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.LinkedList;
import java.util.Map;
import java.util.Queue;
public class Main {
static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
static int[] visited;
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
int cnt = 1;
visited[start] = cnt++;
while (!queue.isEmpty()) {
Integer poll = queue.poll();
if (graph.get(poll) != null) {
for (int neighbor : graph.get(poll)) {
if (visited[neighbor] != 0) {
continue;
}
queue.add(neighbor);
visited[neighbor] = cnt++;
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int i = 0; i < split[1]; i++) {
int[] vertex = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
graph.putIfAbsent(vertex[0], new ArrayList<>());
graph.putIfAbsent(vertex[1], new ArrayList<>());
graph.get(vertex[0]).add(vertex[1]);
graph.get(vertex[1]).add(vertex[0]);
}
for (ArrayList<Integer> nodes : graph.values()) {
nodes.sort(Collections.reverseOrder());
}
visited = new int[split[0] + 1];
bfs(split[2]);
for (int i = 1; i < visited.length; i++) {
System.out.println(visited[i]);
}
}
}문제를 풀어보자면 graph에 입력받은 간선에 따라 값을 모두 넣어주되, 넣고 난 다음에는 내림차순으로 정렬을 한번씩 진행해주고 이후에는 BFS를 돌리면서 현재 값별로 순서를 넣어주고 이후 1부터 정점까지 for문을 돌려주면서 방문 순서를 찍어주면 끝이다.
이전 문제와 다른 점은 방문 순서가 역순이라는 것 외에는 간선이 전혀 업는 정점에서부터 시작하는 경우도 있으므로, Nullpointer Exception를 피하기 위해 if 한번 더 걸어줘야 한다
Leave a Reply