import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int n, m, k, x;
public static ArrayList<ArrayList<Integer>> graph
= new ArrayList<ArrayList<Integer>>();
// 모든 도시에 대한 최단 거리 초기화
public static int[] d = new int[300001];
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()); // 도시의 갯수
m = Integer.parseInt(st.nextToken()); // 도시의 갯수
k = Integer.parseInt(st.nextToken()); // 거리 정보
x = Integer.parseInt(st.nextToken()); // 출발 도시의 번호
// 그래프 및 최단 거리 테이블 초기화
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<Integer>());
d[i] = -1;
}
// 도시 끼리의 단방향 연결 정보
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a =Integer.parseInt(st.nextToken());
int b =Integer.parseInt(st.nextToken());
graph.get(a).add(b);
}
// 출발 도시까지의 거리는 0으로 설정
d[x] = 0;
// BFS
Queue<Integer> q = new LinkedList<Integer>();
q.offer(x);
while (!q.isEmpty()) {
int now = q.poll();
for (int i = 0; i < graph.get(now).size(); i++) {
int nextNode = graph.get(now).get(i);
if (d[nextNode] == -1) {
d[nextNode] = d[now] + 1;
q.offer(nextNode);
}
}
}
// 최단 거리가 K 인 모든 도시의 번호를 오름차순 출력
boolean check = false;
for (int i = 1; i <= n; i++) {
if (d[i] == k) {
System.out.println(i);
check = true;
}
}
// 최단거리인 K인 도시가 없으면 -1 출력
if (!check) {
System.out.println(-1);
}
}
}
1. BFS 사용을 떠올린다.
2. 최단 거리가 K인 모든 도시들의 번호가 필요하다.
3. 입력받은 도시의 연결 정보 graph에 담는다.
4. 최대 30,000개의 도시가 가능, 모든 도시의 거리를 -1으로 초기화한다.
5. 출발 도시의 거리는 0으로 설정.
6. Queue 자료구조에 시작도시를 넣고 BFS를 수행한다.
7. Queue가 빌때까지 해당 도시에 연결된 도시에 방문한 적이 없으면 해당 도시에 현재 도시의 d에서 +1 시키고 다시 큐에 넣는다.
8. 위의 과정을 수행하면 d배열에 거리가 담기게 되고 배열에서 k값과 같은 도시를 오름차순으로 출력한다.
9. 만약에 존재하지않으면 -1출력
- bfs/dfs 이해가 잘 안된다 ....
- 이거 한 문제도 코드 보고 따라가는데도 어렵다 .
반응형
'PS > boj' 카테고리의 다른 글
boj)2606 - 바이러스 (0) | 2020.09.03 |
---|---|
boj)1260 - DFS와 BFS (0) | 2020.09.03 |
boj)1459 - 걷기 (0) | 2020.08.31 |
boj)12018 - Yonsei TOTO (0) | 2020.08.31 |
boj)2012 - 등수 매기기 (0) | 2020.08.31 |