DFS

1068-트리

2023.03.06

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 와... 이문제는 트리를 어떻게 만들어야 하는지 몰라서 시간을 많이 잡아먹은 문제였다. 나는 트리를 2차원 배열을 사용하여 각각 해당하는 노드의 위치를 넣어준 후, DFS 알고리즘을 사용하여 노드를 탐방하면서 지워야 할 숫자가 나오면 그 부분은 스택에 추가시키지 않는 방향으로 코드를 만들어보았다. package Making; import java.io.BufferedReader; import..

알고리즘

BFS와DFS 알고리즘

2023.02.04

BFS 알고리즘이란 너비 우선 탐색이라고 부르며 그래프에서 가장 가까운 노드부터 탐색해 점점 거리를 벌려가는 알고리즘이다. 이 알고리즘을 사용하기위해 Queue를 사용한다. Queue는 FIFO구조이기 때문에 이 구조를 이용하여 알고리즘을 만들면 BFS의 시작점이 중간에 있으면 노드의 방문을 그려보면 동심원으로 이루어지게 된다. DFS 알고리즘은 BFS 알고리즘을 그대로 Queue가 아닌 스택으로 사용하여 구현한 알고리즘이다. 아쉬운점은 처음 시작점에서 DFS 순서대로 이동하면 시작점에서 이동한 거리가 비례해서 증가하지 않는다는 것이다. 이렇게 BFS와 DFS가 어떤 방식으로 구현되는지 알아보았고, 이 알고리즘을 코드로 써본다면 아래와 같은 코드가 될 것이다. from collections import ..

1068-트리

BFS와DFS 알고리즘

티스토리툴바