전체 글

문제 소개조금 복잡한 문제였다. 이모티콘, 클립보드에 대한 조건이 생각할 것이 많았다.문제 풀이BFS를 활용해서 풀었고, 이모티콘, 클립보드, 시간을 queue에 넣어줬다. 또한 방문은 visited 2차원 배열을 사용했다. 왜냐하면 클립보드에 저장한다는 특수한 조건이 있어서 2차원 배열로 저장했다.import Foundation let s = Int(readLine()!)! var visited = Array(repeating: Array(repeating: false, count: 1001), count: 1003) visited[1][0] = true var queue = [(1, 0, 0)] var idx = 0 while queue.count > idx { let emoji = queue[idx..

문제 소개https://www.acmicpc.net/problem/13913DFS를 하기에는 너무많은 경우의 수가 있으니 BFS로 풀어야 한다고 생각했다. 문제 풀이숫자에 _를 붙여서 하면 더 가독성이 좋았다. visited를 활용하여 이전 값을 저장했다.let nk = readLine()!.split(separator: " ").map { Int($0)! } let (n, k) = (nk[0], nk[1]) var visited = Array(repeating: -1, count: 100_001) var queue = [(n, 0)] var index = 0 visited[n] = 0 while queue.count > index { let current = queue[index].0 let time ..

문제 소개섬들을 연결하는 최소길이의 다리를 만드는 문제이다. 문제 풀이이 문제에서 풀어야할것은 두가지가 있다. 첫번째는 섬에 번호를 부여하기, 두번째는 최소 다리길이 구하기이다. 둘다 BFS를 활용하여 구했다.import Foundation let n = Int(readLine()!)! var map = [[Int]]() for _ in 0..= idx + 1 { let poped = queue[idx] for direction in directions { let i = poped.0 + direction.0 let j = poped.1 + direction.1 if i >= 0 && i = 0 && j < n && map[i][j] == 1 { if !visited[i][j] { vi..

문제 해석https://www.acmicpc.net/problem/16964dfs로 풀라고 만든 문제이다. dfs방문순서가 맞는지 물어보는 문제이다. 보통은 dfs로 결과를 찾아나가는데, dfs자체를 검증하는 문제는 신선했다.문제 풀이체크하려는 배열에서 우선순위를 priority 딕셔너리 타입으로 만든다음에 저장한뒤 이 우선순위대로 graph를 재배열 하는 방식으로 풀었다. 그 이후 dfs를 돌려(?) 결과값을 비교했다.import Foundation let n = Int(readLine()!)! var graph = Array(repeating: [Int](), count: n + 1) for _ in 1..

문제 소개https://www.acmicpc.net/problem/16940bfs 방문 순서가 올바른 순서인지 판별하는 문제이다. 문제 풀이집합을 활용했다. bfs를 수행한뒤 결과값을 집합에 넣는다. 그리고 결과값과 비교한다.import Foundation let n = Int(readLine()!)! var infos = Array(repeating: [Int](), count: n + 1) for _ in 1.. idx { var count = 0 for element in infos[check[idx]] { if !visited[element] { visited[element] = true count += 1 second.insert(element) } } if second.isEmpty { bre..

문제 소개https://www.acmicpc.net/problem/7576토마토가 다 익는 시간을 구하는 문제이다. 익은 토마토부터 번져나가는(?) 시간을 구하는 것이다. 문제 풀이bfs를 활용하여 풀었다. 문제는 queue를 활용하긴 했지만 removeFirst의 시간복잡도가 O(n)이였기 때문에 시간초과 문제가 났다. 그래서 removeFirst와 똑같은 효과가 나게 하여 index를 활용하여 문제를 풀었다.import Foundation let mn = readLine()!.split(separator: " ").map { Int($0)! } let (m, n) = (mn[0], mn[1]) var box = [[Int]]() var queue = [(Int, Int)]() for i in 0..=..

문제 소개https://www.acmicpc.net/problem/2178미로를 탐색하는 문제이다. 이러한 문제는 가장 최소의 칸수를 구해야 하는 문제이다. 문제 풀이BFS 풀이미로이기 때문에 한가지 길로 깊게 탐색하는 것보다 넓게 탐색하는 방법을 생각해 보았다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) var map = [[Int]]() var graph = Array(repeating: Array(repeating: 0, count: m), count: n) var visited = Array(repeating: Array(repeating: false, ..

문제 소개https://www.acmicpc.net/problem/2667DFS, BFS 로 모두 풀 수 있는 문제여서 두가지 방법을 사용해 보았다. 문제 풀이DFS 풀이우선 dfs를 활용한 풀이는 재귀함수를 사용했다.import Foundation let n = Int(readLine()!)! var visit = Array(repeating: Array(repeating: false, count: n), count: n) var graph = [[Int]]() for _ in 0..