본문 바로가기

BFS2

그래프 탐색하기 : BFS와 DFS 그래프와 트리는 정점(Node)과 간선(Edge)으로 이루어진 자료구조입니다. 점과 선을 통해 데이터를 저장하기 때문에, 그래프의 경우 도로, 전력망, 네트워크 등 우리가 살고있는 실제 세계를 모델링하는데 많이 사용되며 트리의 경우 컴퓨터의 디렉토리와 같은 계층 구조를 모델링하는데 사용됩니다. 어떤 트리나 그래프에서 특정 노드를 찾기 위해서는 구조 전체를 탐색할 필요가 있습니다. 기존 자료구조의 형식이나 특징에 따라 효율적인 탐색을 할 수 있도록 하는 몇 가지 방법이 있는데, 대표적으로 BFS(Breadth-First Search)와 DFS(Depth-First Search) 두 가지가 있습니다. 오늘 포스팅에서는 이 두 가지 탐색 방법들의 특징과 각 방법을 사용하기 좋은 케이스 등을 알아보겠습니다. B.. 2023. 3. 24.
[C++] 백준 13549번: 숨바꼭질 3 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 규칙에 따라 특정 위치로 이동하는 최단시간을 찾는 숨바꼭질 문제 시리즈입니다. 문제에서 시작지점에 위치한 수빈이는 1초의 시간을 소모하여 +1 또는 -1 로 움직이거나, 0초의 시간을 소모하여 현재 인덱스의 두 배 지점으로 순간이동을 할 수 있습니다. 이동 방식의 가중치가 다르기 때문에 다익스트라를 사용하셔도 되고, 이 문제의 경우 단순 bfs로 해결할 수도.. 2021. 10. 7.