문제
- 다음 그래프에서 1번 정점에서 각 정점으로 가는 최소 이동 간선수를 출력하세요.
입력
- 첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.
- 그 다음부터 M줄에 걸쳐 연결정보가 주어진다.
출력
- 1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례로 출력하세요.
입출력 예제
풀이방식
이번 문제는 큐, 재귀함수를(을) 사용하여 푸는 문제이다.
재귀함수에 대한 자세한 설명은 아래 글을 참조하길 바랍니다.
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)
문제 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요. 입력 첫 번째 줄은 정수 N(3
silverji.tistory.com
설계과정
1. 1번부터 N번까지 가는 최소 거리를 저장하는 배열을 생성한다.
2. 큐를 이용해서 해당 배열에 최소 거리를 저장한다.
3. 이 때, A 노드에서 다음 노드로 갈 때에는 1개의 거리가 추가되므로 +1을 해준다.
4. 위 과정을 반복하여 각 정점으로 가는 최소 간선수를 출력한다.
풀이과정
1. 전역으로 각 변수들을 선언하고 일부 값들을 입력받는다.
- N : 노드의 개수를 의미한다.
- M : 간선의 개수를 의미한다.
- ch[ ] : 방문 여부를 확인할 값이 들어있는 배열이다.
- dis[ ] : 1번 ~ N번까지 가는 최소 거리값을 저장한다.
- graph : 연결 정보를 저장한다. (연결이 가능한 노드들을 저장한다.)
- 여기서 graph는 ArrayList<Integer> 를 저장할 수 있는 객체를 저장하는 ArrayList로 선언한다.
- 연결 정보를 저장할 때에 graph에서 A 값을 가져온 후에 그 뒤에 B 값을 더해서 넣는다.
2. BFS 메소드 구현으로 넘어가보자.
3. 큐를 선언한다.
- 큐에는 각 정점들이 들어갔다 나오며 dis 배열에 최소 거리값을 저장한다.
4. ch[] 배열의 첫번째에 1을 넣는다.
- 맨 처음에 자신의 노드는 방문을 반드시 해야하기 때문이다.
- 처음이 0이 아닌 이유는, 1번 ~ N번 까지의 정점 노드를 구하기 위해 N+1 까지로 배열의 크기를 잡았기 때문이다.
5. div[] 배열의 첫번째에 0을 넣는다.
- 1번 노드는 자기 자신을 방문할 수 없으므로 0으로 값이 들어간다.
6. Q가 비어있지 않으면 계속해서 도는 while 문을 선언한다.
7. 현재의 정점 값을 저장하는 cv를 선언하고, 큐 맨 앞에 있는 값을 꺼내어 넣는다.
- poll() : 큐 맨 앞에 있는 값 반환 후 삭제한다.
8. cv번 ArrayList와 nv를 하나씩 대응하여 방문 여부를 확인한다.
9. 방문한 적이 없으면 1을 넣고 해당 정점을 큐에 넣는다.
10. 다음 정점을 가기 위해서 dis[cv] + 1 한 값을 dis[nv] 에 넣는다.
- dis[cv] : 현재 정점 노드
- dis[nv] : 다음 정점 노드
아래 이미지를 통해 자세히 이해해보자.
문제에 그래프는 다음과 같다.
1. 맨 처음으로 1번 정점 노드에 방문했을 때에 dis 배열은 다음과 같이 값이 들어간다.
- 자기 자신에게 방문할 수 없기에 1번은 0의 값이 들어간다.
2. 1에서 갈 수 있는 다음 정점 노드는 3과 4가 있다. 그러므로 dis 배열과 큐에 각각 다음과 같은 값이 들어간다.
- 1에서 각 정점 노드로 갈 때에 거리는 1만큼 추가된다.
- 큐에는 3과 4가 들어가있다.
3. 3에서 갈 수 있는 정점 노드는 4이다. 그러나 4는 이미 방문했다고 체크되었으므로, 큐에서만 3이 빠진다.
4. 이제 4에서 갈 수 있는 정점 노드인 5와 6으로 각각 가보자.
- 4에서 이동한 거리이므로 4에 있는 값에 1을 더한 2를 넣어준다.
- 이제 4는 큐에서 빠진다.
5. 5에서 갈 수 있는 정점이 없으므로 큐에서 5가 빠지고, 6에서 갈 수 있는 정점인 2로 가보자.
- 일단 6도 큐에서 뺀다.
- 2는 6에서 1이라는 거리가 추가되는 것이므로 6의 값인 2에서 1을 더한 3을 2에 넣어준다.
6. 모든 경로가 진행되었으니 출력 형태에 맞게 출력해준다.
해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.
'알고리즘 > 인프런' 카테고리의 다른 글
| 섹션 8. DFS, BFS 활용 2. 바둑이 승차(DFS) (0) | 2022.12.01 |
|---|---|
| 섹션 8. DFS, BFS 활용 1. 합이 같은 부분집합(DFS : 아마존 인터뷰) (0) | 2022.11.29 |
| 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 13. 경로탐색(인접리스트, ArrayList) (0) | 2022.11.19 |
| 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 12. 경로탐색(DFS) (0) | 2022.11.19 |
| 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 10. Tree 말단노드까지의 까장 짧은 경로(BFS) (0) | 2022.11.18 |
