2024. 1. 22. 19:47ㆍ알고리즘
♣ 문제
♣ 문제 이해
이전 글인 너비우선탐색을 이용하여 해결할 수 있는 문제이다.
https://jy-deeplearning.tistory.com/72
BFS(너비 우선 탐색, 백준 알고리즘 16953번)
♣ 문제 ♣ 문제 이해 주어진 정수 A를 정수 B로 바꾸는 문제로, A*2를 하거나 str(A)+'1'을 해서 숫자를 바꿔간다. 첫 번째 예제를 보면 2 -> 4 -> 8 -> 81 -> 162 루트를 통해서 162를 만들 수 있고, 4번의 숫
jy-deeplearning.tistory.com
주어진 트리의 루트는 1이고, 1부터 시작하여 노드들이 연결된다. 이때 각 노드의 부모를 출력하는 문제이다.
위의 첫 번째 예제를 보면 트리는 아래와 같다.
노드 1을 제외하고 2부터 마지막 7까지의 부모 노드를 출력하면 4 6 1 3 1 4 가 답이 된다.
♣ 문제 해결 방법
이 문제에서는 위의 그래프를 리스트로 어떻게 구현하느냐가 중요하다. 노드 1부터 시작하여 너비탐색을 하면서 서로 연결된 노드를 리스트에 구현하는 것을 생각하는 게 어려웠다.
n은 주어진 트리의 수를, visited는 주어진 트리들을 방문했는지 유무를, answer은 각 노드의 부모 트리를, e는 각 노드가 연결되어 있는 노드를 나타낸 것이다.
for문을 사용하여 연결된 노드 쌍을 입력하면
아래와 같은 e가 형성된다.
e에는 빈 리스트를 n+1개 넣었기 때문에 맨 앞의 리스트는 노드 0 이므로 무시하고, 그 다음 노드부터 살펴본다.
[6, 4]는 노드1과 연결되어 있는 노드6, 4를 의미한다. [4]는 노드[2]와 연결된 노드4를 의미한다. 이런 식으로 각 노드가 어떤 노드들과 연결되어 있는지를 확인할 수 있다.
연결된 노드들을 만든 뒤, 너비우선탐색을 함수로 정의한다. queue를 이용하여 부모 노드 1을 deque에 넣고, visited[1]=True로 만듦으로써 1번 노드를 방문했다는 것을 표시한다. 그리고 queue 안에 있는 요소들을 하나씩 빼는데, 이 빠진 요소가 부모 노드가 된다. 그리고 앞에서 만들어둔 연결된 노드들 리스트 안에서 x의 자식 노드들을 방문하면서 visited를 True로 만든다. 또한 방문한 자식 노드들을 queue에 추가한다.
v에 첫 부모 노드인 1을 넣어서 함수 bfs를 실행하면 아래와 같은 결과가 출력된다.
첫 번째 부모 노드인 1부터 방문하기 시작하여 1의 자식 노드인 6, 4를 방문하고, 6, 4의 자식 노드들을 또 추가한다. 이런 방식으로 너비우선탐색을 이어간다. 또한 해당하는 부모 노드를 answer에 넣는다.
visited가 모두 True가 되면(0번 노드는 존재하니까 False 유지) 더 이상 queue에 새로운 요소가 추가되지 않고, queue에 popleft가 계속 적용되다가 모두 다 빠져나가면 코드가 종료된다.
answer을 차례대로 출력하면 각 노드의 부모 노드를 확인할 수 있다.
♣ 전체 코드
'알고리즘' 카테고리의 다른 글
| Dijkstra(데이크스트라 알고리즘, 백준 알고리즘 18352번) (0) | 2024.02.06 |
|---|---|
| DFS(깊이우선탐색, 백준 알고리즘 4963번) (0) | 2024.01.29 |
| BFS(너비 우선 탐색, 백준 알고리즘 16953번) (0) | 2024.01.16 |
| 트리 만들기(백준 14244번) (1) | 2024.01.09 |
| 신장트리(백준 알고리즘 9372번) (0) | 2024.01.07 |