이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/107 이곳을 확인해주세요! 깊이우선탐색(DFS) 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식 탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고, 다시 돌아가서 다른 인접노드의 자식들을 모두 탐색합니다. 탐색 노드의 가장 깊은 높드까지 다 탐색해야 다음 인접노드를 탐색할 수 있습니다. 구현 탐색할 그래프 미리 만들어두기 let graph: [String: [String]] = [ "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], "D" : ["B"], "E" : ["B"], "F" : ["C"], ] 깊이우선탐색을 하는 ..

import Foundation /// 케빈 베이컨 수 : 모든 사람과 케빈 베이컨 게임을 했을 때 나오는 단계의 합 /// BOJ 유저가 5명이고, 1-3, 1-4, 2-3, 3-4, 4-5가 친구인 경우 /// 1은 친구와 이어지기 위해 1-3-2, 1-3, 1-4, 1-4-5 이런 단계를 거친다. 즉 케빈 베이컨 수는 2 + 1 + 1 + 2 = 6이다. /// BOJ 유저의 수와 친구관계가 입력으로 주어졌을 때, 케빈 베이컨 수가 가장 작은 사람을 구하는 프로그램을 작성하시오. /// N : 유저의 수 /// M : 친구관계의 수 let NM = readLine()!.components(separatedBy: " ").map { Int($0)! } let N = NM[0] let M = NM[1]..

이 글은 개인적인 공부를 위해 작성된 글임을 밝힙니다. 자세한 내용은 https://babbab2.tistory.com/106 이곳에서 확인해주세요! 너비우선탐색(BFS) Breadth-First Search 인접한 노드를 우선하여 탐색하는 방식입니다. 탐색 노드로부터 인접한 노드를 먼저 탐색하고, 다 탐색하면 인접한 노드의 인접한 노드들부터 탐색합니다. 따라서 같은 레벨에 있는 노드들부터 탐색하는 것처럼 보입니다. 참고로 왼쪽부터 탐색할지, 오른쪽부터 탐색할지 같은 순서는 중요하지 않습니다. 구현 1. 탐색할 그래프 미리 만들어두기 let graph: [String: [String]] = [ "A" : ["B", "C"], "B" : ["A", "D", "E"], "C" : ["A", "F"], "D"..