import Foundation let MNH = readLine()!.split(separator: " ").map { Int($0)! } let M = MNH[0] // 열 let N = MNH[1] // 행 let H = MNH[2] // 면 var board = [[[Int]]]() for _ in 0..

import Foundation let nm = readLine()!.components(separatedBy: " ").map { Int($0)! } let n = nm[0] let m = nm[1] var board = [[Int]]() for _ in 0..

BFS(Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 구현방법 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 4. 큐가 빌 때까지 2번을 반복 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N). 예시코드 import Foundation let board: [[Int]] = [ [1,1,1,0,1,0,0,0,0,0], [1,0,0,0,1,0,0,0,0,0], [1,1,1,0,1,0,0,0,0,0], [1,1,0,0,1,..

import Foundation /// 1: 이동가능, 0: 이동불가능 /// (1, 1)에서 (N, M)의 위치로 이동하는 최단거리 구해라 /// dfs 알고리즘 특성 상 최단거리를 찾으려면 완전 탐색을 하고 가장 작은 값을 선택해야 하는데 /// 경로가 아주 많을 수도 있으므로 시간복잡도가 매우 커진다. /// 그래서 bfs로 풀어야한다. let NM = readLine()!.components(separatedBy: " ").map { Int($0)! } let N = NM[0] let M = NM[1] let dx = [0, 0, -1, 1] let dy = [-1, 1, 0, 0] // 상하좌우 // 0과 1의 정보가 담긴 보드 var board = [[Int]]() // 방문한 좌표를 담을 배..

import Foundation /// N : 컴퓨터의 수 (정점) /// M : 네트워크 상에서 직접 연결되어 있는 컴퓨터쌍의 수 (간선) let N = Int(readLine()!)! let M = Int(readLine()!)! var graph = [String: [String]]() var cnt = 0 for i in 0..

import Foundation let NMV = readLine()!.components(separatedBy: " ").map { Int($0)! } let N = NMV[0] let M = NMV[1] let V = NMV[2] var graph = [String: [String]]() initializeGraph() for _ in 1...M { let AB = readLine()!.components(separatedBy: " ") let A = AB[0] let B = AB[1] graph[A]?.append(B) graph[B]?.append(A) } printArray(DFS(start: String(V))) printArray(BFS(start: String(V))) func DFS(st..

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"..