문제 내용은 입력으로 그래프 구조를 받아, 시작 위치에서부터 지정된 횟수 만큼 이동했을 때 도달할 수 있는 정점을 오름차순으로 출력해주면 되는데, 없을 경우에는 -1을 출력한다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeSet;
public class Main {
static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
static int[] visited;
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[] 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]);
}
visited = new int[split[0] + 1];
Arrays.fill(visited, -1);
bfs(split[3], split[2]);
TreeSet<Integer> set = new TreeSet<>();
for (int i = 1; i < visited.length; i++) {
if (visited[i] == split[2]) {
set.add(i);
}
}
if (set.isEmpty()) {
System.out.println(-1);
} else {
for (Integer integer : set) {
System.out.println(integer);
}
}
}
public static void bfs(int start, int min) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = 0;
while (!queue.isEmpty()) {
Integer poll = queue.poll();
for (int neighbor : graph.get(poll)) {
if (visited[neighbor] == -1) {
visited[neighbor] = visited[poll] + 1;
queue.add(neighbor);
}
}
}
}
}
문제를 풀어보자면, 먼저 그래프를 구성해주되 단방향이므로 양방향 처리하지 않도록 주의하고 BFS를 돌려줘야 하는데 visited 배열에 방문 순서를 모두 기록해준 후
BFS가 끝나면 최단 거리에 해당하는 항목들을 모두 넣어줘야 하는데 TreeSet을 사용하면 자동 오름차순 정렬이므로 정렬할 필요가 없다.
이후 TreeSet이 비었으면 -1을 출력하고 값이 있으면 차례대로 출력해주면 자동으로 오름차순 된 값만 나오게 된다
Leave a Reply