티스토리 뷰
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 |
링크
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- ㅇㄷㅇㅈ
- 이펙티브자바
- HTTP 완벽가이드
- 이펙티브자바 아이템59
- GCP
- 김영한 http
- Spring Security
- HTTP 완벽 가이드
- dreamcoding
- 드림코딩
- 프로그래머스
- 백기선 스터디
- BOJ
- 모던자바스크립트
- 이펙티브자바 스터디
- 이펙티브자바 아이템60
- 패스트캠퍼스 컴퓨터공학 완주반
- 킹수빈닷컴
- js array
- 가상 면접 사례로 배우는 대규모 시스템 설계 기초
- http
- 김영한 JPA
- 백준
- java
- JPA 연관관계 매핑
- js promise
- JS 딥다이브
- js api
- 프로그래머스 SQL
- REST API
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
글 보관함