1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하시오
6 9
1 3
1 4
2 1
2 5
3 4
4 5
4 6
6 2
6 5
graph.get(0) - []
graph.get(1) - [3,4]
graph.get(2) - [1,5]
graph.get(3) - [4]
graph.get(4) - [5,6]
graph.get(5) - []
graph.get(6) - [2,5]
경로 탐색과 마찬가지로 방문한 정점에 대해서 체크해주는 배열이 필요하다.
여기서 방문 체크 이유는 해당 정점을 방문 했다는게 최단 거리를 구했다는 의미이기 때문이다.
경로 탐색과는 다르게 방문 체크를 푸는 작업을 하지 않아도 된다.
1.최단거리는 BFS라고 생각하면 된다.!
1번 정점에서 한번 만에 가는 정점, 두번 만에~, 세번 만에~ 찾으면된다.
2.레벨말고 dis[] 이용해서 거리를 넣어본다.
dis[3] -> 1번 정점에서 3번 정점으로 가는 최소 거리
1.레벨로 나눠서 몇 레벨만에 갈 수 있는지 구하기
import java.util.*;
public class Main {
static int n, m;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch, dis;
public void BFS(int v) {
Queue<Integer> q = new LinkedList<>();
//루트 노드(1)는 넣어둔다
q.offer(v);
//루트 노드의 레벨은 0
int L = 0;
//1번은 방문처리
ch[1] = 1;
while(!q.isEmpty()) {
//현재의 정점 꺼내기
for(int i = 0; i < q.size(); i++) {
int cv = q.poll();
//현재의 정점에서 갈 수 있는 정점들 확인
for (int nv : graph.get(cv)) {
if(ch[nv] == 0) {
ch[nv] = 1;
q.offer(nv);
System.out.println(nv + " : " + (L + 1));
}
}
}
L++;
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
m = kb.nextInt();
graph = new ArrayList<ArrayList<Integer>>();
//★★★
for(int i = 0; i <= n; i++) {
graph.add(new ArrayList<Integer>());
}
ch = new int[n+1];
//거리 기록해놓는 배열
dis = new int[n+1];
for(int i = 0; i < m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
graph.get(a).add(b);
}
T.BFS(1);
//for(int i = 2; i<=n; i++) System.out.println(i + " : " + dis[i]);
}
}
2.거리 기록해놓는 dis[] 배열 이용하기
dis[nv] = dis[v] + 1; 을 이용해서 거리를 기록해놓기
import java.util.*;
public class Main {
static int n, m;
static ArrayList<ArrayList<Integer>> graph;
static int[] ch, dis;
public void BFS(int v) {//현재 정점은 v
Queue<Integer> queue = new LinkedList<>();
//1번 정점은 방문 처리를 해놓는다.
ch[v] = 1;
//1번 정점에서 1번 정점으로 가는 거리는 0이다.
dis[v] = 0;
//1번 정점을 큐에 삽입한다.
queue.offer(v);
while(!queue.isEmpty()) {
//현재의 정점을 꺼내기
int cv = queue.poll();
//현재의 정점에서 갈 수 있는 정점들 확인
for(int nv : graph.get(cv)) {
//방문했냐 안했냐만 확인
//방문 했으면 dis 배열에 의해 이미 최단거리로 기록이 되있을거임
if(ch[nv] == 0) {
//방문 안했으면 방문 처리 해놓고
//갈 수 있는 해당 정점들을 큐에 넣어준다.
ch[nv] = 1;
queue.offer(nv);
//그리고 갈 수 있는 해당 정점에 현재 정점의 거리 + 1 기록해놓는다.
dis[nv] = dis[cv] + 1;
}
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
n = kb.nextInt();
m = kb.nextInt();
graph = new ArrayList<ArrayList<Integer>>();
//★★★
for(int i = 0; i <= n; i++) {
graph.add(new ArrayList<Integer>());
}
ch = new int[n+1];
//거리 기록해놓는 배열
dis = new int[n+1];
for(int i = 0; i< m; i++) {
int a = kb.nextInt();
int b = kb.nextInt();
graph.get(a).add(b);
}
T.BFS(1);
for(int i = 2; i<=n; i++) System.out.println(i + " : " + dis[i]);
}
}
dis[nv] = 현재의 거리 dis[cv] + 1
1번 정점을 꺼내고 1번 정점에서 갈 수 있는 정점들 확인(3,4)
3번 정점 ch[3] == 0 이므로 ch[3] = 1 방문처리해놓고 3을 큐에 넣음
q [3]
그리고 거리는 dis[3] = dis[1] + 1 = 0 + 1 = 1
4번 정점 ch[4] == 0 이므로 ch[4] = 1 방문처리해놓고 4를 큐에 넣음
q [3,4]
그리고 거리는 dis[4] = dis[1] + 1 = 0 + 1 = 1
3번 정점을 꺼내고 3번 정점에서 갈 수 있는 정점들 확인(4)
4번 정점 ch[4] == 1 이므로 이미 거리가 입력되어있으므로 아무일도 안일어남
q [4]
4번 정점을 꺼내고 4번 정점에서 갈 수 있는 정점들 확인(5,6)
5번 정점 ch[5] == 0 이므로 ch[5] = 1 방문처리해놓고 5를 큐에 넣음
q [5]
그리고 거리는 dis[5] = dis[4] + 1 = 1 + 1 = 2
6번 정점 ch[6] == 0 이므로 ch[6] = 1 방문처리해놓고 6을 큐에 넣음
q [5,6]
그리고 거리는 dis[6] = dis[4] + 1 = 1 + 1 = 2
5번 정점을 꺼내고 5번 정점에서 갈 수 있는 정점들 확인
q [6]
갈 수 있는 정점이 없으므로 아무 일도 안일어남
6번 정점을 꺼내고 6번 정점에서 갈 수 있는 정점들 확인
2번 정점 ch[2] == 0 이므로 ch[2] = 1 방문처리해놓고 2를 큐에 넣음
q [2]
그리고 거리는 dis[2] = dis[6] + 1 = 2 + 1 = 3
2번 정점을 꺼내고 2번 정점에서 갈 수 있는 정점들 확인
1번 5번으로는 갈 수 없음
'Algorithm > inflearn' 카테고리의 다른 글
| 바둑이 승차(DFS) (0) | 2021.10.03 |
|---|---|
| #합이 같은 부분집합(DFS) (0) | 2021.10.03 |
| ★경로 탐색(인접리스트) (0) | 2021.09.30 |
| ★경로 탐색(인접 행렬, DFS) (0) | 2021.09.30 |
| Tree 말단노드까지의 가장 짧은 경로(BFS) (0) | 2021.09.30 |