BFS

[99클럽 코테 스터디 10일차 TIL] 특정 거리의 도시 찾기 - 백준 18352

10일차 오늘도 BFS 문제다. https://www.acmicpc.net/problem/18352어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다.모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.[입력]첫째 줄에 도시..

[99클럽 코테 스터디 9일차 TIL] 나이트의 이동 - 백준 7562

오늘의 문제 키워드가 DFS/BFS였지만 이번에는 명확하게 BFS를 활용하는 문제였다. https://www.acmicpc.net/problem/7562체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?[입력]입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, ..

[99클럽 코테 스터디 8일차 TIL] 촌수계산 - 백준 2644

오늘 주제는 DFS/BFS이다. https://www.acmicpc.net/problem/2644우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.[입력]사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 ..

[99클럽 코테 스터디 5일차 TIL] 알고리즘 수업 - 너비 우선 탐색 1 - 백준 24444

어제는 DFS라서 혹시나 했더니 역시나 오늘은 BFS다. https://www.acmicpc.net/problem/24444오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다.아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} ..

[Algorithm] Breadth-First Search(BFS)

오늘의 알고리즘 Topic은 Breadth-first search(너비우선탐색)입니다.사실 BFS라고 더 많이 불리고 있습니다. BFS하면 짝꿍 DFS도 빠질 수 없습니다.DFS는 이후 게시글에서 알아보도록하고 오늘은 BFS를 먼저 살펴보겠습니다.특징BFS의 기본 개념은 Tree 구조에서 파생되었고, Tree의 노드를 순회하는 방식 중에 하나입니다.어떠한 자료구조를 순회할 때는 항상 기준이 중요합니다. BFS의 기준은 바로 현재 노드의 Depth입니다. Tree는 기본적으로 Depth라는 개념이 있습니다.Root 노드로부터 몇번째 자식노드냐에 따라 Depth가 정해집니다.위 사진에서 최상단의 붉은 원이 Root노드이며, 11 노드는 Root 노드로부터 3번째 노드이므로 Depth가 3입니다.Tree 노드..