문제 https://www.acmicpc.net/problem/1753 풀이 다익스트라 입문 문제이다. 단, 스위프트로 풀려면 힙을 직접 구현해야 한다. 입력으로 주어지는 엣지의 웨이트가 모두 같다는 조건이 없으므로, BFS가 아닌 다익스트라로 탐색해야 한다. 코드 import Foundation struct Heap { var heap: [(Int, Int)] = [] func isEmpty() -> Bool { return heap.isEmpty ? true : false } mutating func insert(_ value: (Int, Int)) { heap.append(value) var currentIndex = heap.count - 1 while currentIndex > 0 { let parentIndex = (currentIndex - 1) / 2 if heap[currentIndex].1 < heap[parentIndex].1 { heap.swapAt(currentIndex, parentIndex) currentIndex = parentIndex } else { break } } } mutating func deleteMin() -> (Int, Int) { if heap.isEmpty{ return (0, 0) } let min = heap[0] heap[0] = heap[heap.count - 1] heap.removeLast() var currentIndex = 0 while true { let leftChildIndex = 2 * currentIndex + 1 let rightChildIndex = 2 * currentIndex + 2 if leftChildIndex >= heap.count { break } var minChildIndex = leftChildIndex if rightChildIndex < heap.count && heap[rightChildIndex].1 < heap[leftChildIndex].1 { minChildIndex = rightChildIndex } if heap[minChildIndex].1 < heap[currentIndex].1 { heap.swapAt(currentIndex, minChildIndex) currentIndex = minChildIndex } else { break } } return min } } func dijkstra(k: Int) { var heap = Heap() heap.insert((k, 0)) distanceTable[k] = 0 while !heap.isEmpty() { let edge = heap.deleteMin() if distanceTable[edge.0] < edge.1 { continue } for node in graph[edge.0] { let cost = edge.1 + node.1 if cost < distanceTable[node.0] { distanceTable[node.0] = cost heap.insert((node.0, cost)) } } } } let ve = readLine()!.split(separator: " ").map { Int(String($0))! } let k = Int(readLine()!)! var graph = [[(Int, Int)]](repeating: [], count: ve[0] + 1) for _ in 0..<ve[1] { let uvw = readLine()!.split(separator: " ").map { Int(String($0))! } graph[uvw[0]].append((uvw[1], uvw[2])) } var distanceTable = [Int](repeating: 300_001, count: ve[0] + 1) dijkstra(k: k) for i in 1...ve[0] { if distanceTable[i] == 300_001 { print("INF") } else { print(distanceTable[i]) } }

문제 https://www.acmicpc.net/problem/14003 풀이 LIS(Longest Increasing Subsequence)라고 하는 유명한 DP 문제이다. 이 문제 외에도 연계된 문제들이 많으니 1번(BOJ 11053)부터 차례대로 풀면 어느새 여기까지 풀게 된다. 이 문제들은 총 2가지 기준으로 분류된다. 첫 번째 기준은 O(n²), O(nlogn) 두 번째는 LIS 출력 여부이다. 이 중에 O(nlogn) 알고리즘을 사용하고 LIS를 직접 출력해야 하는 문제가 이 문제이다. 원래는 Swift로 작성하려 했지만, 백준의 입력시간 문제 때문에 Swift론 입력 횟수가 적은 O(n²)문제를 풀고 O(nlogn) 문제는 C++로 작성하였다. 기본적인 알고리즘 콘셉트는 다음과 같다. ...

문제 https://www.acmicpc.net/problem/16398 풀이 모든 행성을 연결해야 하고, 그 비용을 최소로 하려면 최소 스패닝 트리(MST)를 찾아야 한다. 따라서 알고리즘의 흐름은 다음과 같아진다. 2차원 배열로 입력받은 플로우 관리비용을 정렬한다. Kruskal 알고리즘을 이용해 최소 스패닝 트리를 구한다. 여기서 에지(플로우 관리비용)의 정보가 2차원 배열로 입력되므로 배열을 순회하여 (노드, 노드, 비용)꼴의 튜플 배열로 만들어 정렬했다. 2차원 배열의 각 인덱스가 노드를 특정하므로 이렇게 하는 것이 최선이라 생각했다. 코드 func find(_ a: Int) -> Int { if parent[a] != a { parent[a] = find(parent[a]) } return parent[a] } func union(_ a: Int, _ b: Int) { let pa = find(a) let pb = find(b) if pa < pb { parent[pb] = pa } else { parent[pa] = pb } } import Foundation let n = Int(readLine()!)! var graph: [[Int]] = [] var edges: [(Int, Int, Int)] = [] var parent = Array(0..<n) var answer: Int = 0 for _ in 0..<n { graph.append(readLine()!.split(separator: " ").map { Int(String($0))! }) } for row in 0..<n { for column in 0..<row { edges.append((row, column, graph[row][column])) } } edges.sort(by: { $0.2 < $1.2 } ) for edge in edges { if find(edge.0) != find(edge.1) { union(edge.0, edge.1) answer += edge.2 } } print(answer)

문제 https://www.acmicpc.net/problem/4195 풀이 전형적인 Union-Find 문제이지만, 각 원소들이 정수가 아닌 문자열로 구성되어 있는 특징이 있다. 정수를 문자열로 대응시키는 것은 Dictionary를 쓰면 쉽게 할 수 있으므로 다음과 같은 방식으로 알고리즘이 진행된다 입력값(문자열 2개)에 대해 각 문자열이 Dictionary에 대응되는 Value가 있는지 판단한다. 1에서 없다면 Dictionary에 [String:Integer] 꼴로 매핑한다. 있다면 그냥 넘어간다. 매핑이 끝났다면, 들어온 두 문자열로 union(a, b) 연산을 하고 그 집합 내부의 원소의 개수를 카운트한다. 여기서 문제는 3번이다. 어떻게 해야 효율적으로 집합 내부의 원소를 카운트 할 수 있을까? ...

문제 https://www.acmicpc.net/problem/1726 풀이 로봇이 바라보는 방향에 따라서 갈 수 있는 노드가 달라진다 -> 3차원 그래프다 (세로 m, 가로 n, 높이가 4인) 이 발상만 빠르게 해낸다면 평범한 BFS 문제가 된다. 하나의 노드에서 최대 5개의 노드와 연결이 가능하다(회전 2방향, 전진 3방향) 하지만 2칸 이상 전진했을때, 앞선 칸이 1이면 넘어가지 못한다. (점프를 할 수 없다) 이것만 주의하고 BFS 탐색을 하면 쉽게 결과를 낼 수 있다. 코드 # east 0 west 1 south 2 north 3 from collections import deque def bfs(start): bfsQ = deque() bfsQ.append(start) isVisited[start[0]][start[1]][start[2]] = True count[start[0]][start[1]][start[2]] = 0 while(bfsQ): node = bfsQ.popleft() currentDir = node[2] currentCount = count[node[0]][node[1]][node[2]] if node == end: return currentCount for dir in rotate[currentDir]: if end == [node[0], node[1], dir]: return currentCount + 1 if isVisited[node[0]][node[1]][dir]: continue isVisited[node[0]][node[1]][dir] = True count[node[0]][node[1]][dir] = currentCount + 1 bfsQ.append((node[0], node[1], dir)) if currentDir == 0: moves = [(0, 1), (0, 2), (0, 3)] elif currentDir == 1: moves = [(0, -1), (0, -2), (0, -3)] elif currentDir == 2: moves = [(1, 0), (2, 0), (3, 0)] else: moves = [(-1, 0), (-2, 0), (-3, 0)] for move in moves: row = node[0] + move[0] column = node[1] + move[1] if end == [row, column, currentDir]: return currentCount + 1 if row < 0 or row >= m or column < 0 or column >= n: continue if isVisited[row][column][currentDir]: continue if graph[row][column] == 1: break isVisited[row][column][currentDir] = True count[row][column][currentDir] = currentCount + 1 bfsQ.append((row, column, currentDir)) graph = [] rotate = {0: [2, 3], 1: [2, 3], 2: [0, 1], 3: [0, 1]} m, n = map(int, input().split()) for _ in range(m): graph.append(list(map(int, input().split()))) start = list(map(int, input().split())) end = list(map(int, input().split())) for i in range(3): start[i] -= 1 end[i] -= 1 isVisited = [[[False] * 4 for i in range(n)] for j in range(m)] count = [[[0] * 4 for i in range(n)] for j in range(m)] print(bfs(start))

문제 https://www.acmicpc.net/problem/3055 풀이 입력으로 그래프가 주어지고, 어느 칸에서 BFS를 시작해야하는지 알려준다. 문제를 읽어보면 고슴도치와 물 둘 다 BFS 탐색을 해야 하는 것을 알 수 있다. 주의할 점은 예제에는 초기에 물인 칸이 1개밖에 없지만 문제를 읽어보면 1칸이라는 제약조건이 없다. 따라서 물이 여러칸일 때도 생각하고 프로그래밍을 해야 한다. 처음에 두 가지 생각을 했다. BFS탐색을 각각 따로 하는 방법 고슴도치를 먼저 BFS 탐색시켜서 그래프에 각 칸마다 몇번째 이동에 도달하는지 검사한다. 다음에 물을 BFS 탐색해서 1의 결과가 가능한지를 판단한다. 고슴도치와 물을 단계별로 번갈아가면서 BFS 탐색 하는 방법 ...

문제 https://www.acmicpc.net/problem/7576 풀이 처음엔 무난한 BFS 문제라고 생각했다. 처음부터 익어있는 토마토(루트 토마토라고 하겠다.)가 들어있는 칸을 알아낸 다음에 반복문으로 BFS를 적용하고, 루트 토마토를 할 때마다 만약 칸에 더 적은 숫자가 들어 갈 수 있다면 숫자를 업데이트 하는 식으로 문제를 풀었다. 그랬더니 시간초과가 나온다. 쓸데없는 연산이 너무 많아서 그렇다. 정확한 풀이는 BFS 큐를 처음 만들때부터 모든 루트 토마토를 넣어서 초기화 하는 것이었다. 그러면 모든 루트 토마토를 기준으로 동시에 탐색할 수 있으니까. 칸을 탐색할때도 더 높은 숫자가 나오면 그 칸은 큐에 넣을 필요가 없다. 이미 전에 했던 탐색이 더 좋은 결과를 가져다 주었을태니 ...

문제 https://www.acmicpc.net/problem/2667 풀이 그래프가 입력으로 주어지고, 각 노드마다 탐색의 범위가 상하좌우로 제한된다. 앞서 해결했던 미로 탐색과 순열 사이클을 섞어놓은 듯 한 문제이다. 따라서 다음과 같은 과정으로 출력값을 얻었다. 전체 그래프를 탐색하는 2중 반복문을 작성한다. 방문하지 않은 노드가 나올 때마다 그래프 탐색(DFS, BFS)를 실시한다. 각 그래프를 탐색했을때 노드의 개수를 저장하고 정렬한 다음에 출력한다. 코드 from collections import deque def bfs(v): bfsQ = deque() bfsQ.append(v) isVisited[v[0]][v[1]] = True moves = [(1, 0), (-1, 0), (0, 1), (0, -1)] count = 1 while bfsQ: node = bfsQ.popleft() for move in moves: row = node[0] + move[0] column = node[1] + move[1] if row < 0 or row >= n or column < 0 or column >= n: continue if graph[row][column] != 0 and not isVisited[row][column]: isVisited[row][column] = True bfsQ.append((row, column)) count += 1 return count n = int(input()) graph = [] for _ in range(n): temp = input() graph.append(list(map(int, temp))) isVisited = [[False] * n for i in range(n)] area = [] for row in range(n): for column in range(n): if graph[row][column] == 1 and not isVisited[row][column]: area.append(bfs((row, column))) area.sort() print(len(area)) for i in range(len(area)): print(area[i])

문제 https://www.acmicpc.net/problem/2331 풀이 수열을 만드는 반복문을 만든다. 도중에 기존에 있는 원소와 같은 원소가 나오면 반복문을 종료한다. 처음으로 나온 같은 원소의 인덱스를 출력한다. (인덱스는 0부터 시작이기에 더하고 뺄 필요가 없다.) 너무 간단하게 풀렸는데 시간복잡도가 별로 좋아보이진 않는다. 더 좋은 방법이 있을듯 싶다. 코드 a, p = map(int, input().split()) seq = [a] while True: element = 0 for i in str(seq[-1]): element += (int(i) ** p) if element in seq: break seq.append(element) print(seq.index(element))

문제 https://www.acmicpc.net/problem/1697 풀이 입력으로 수빈이와 동생의 위치, 그리고 수빈이가 이동할 수 있는 제약조건을 알려준다. 수빈이의 위치보다 동생의 위치가 더 앞에 있거나 같을때는 (n >= k) 뒤로 가는 방법이 한칸 이동하는 것 밖에 없으므로 n - k 로 쉽게 결과를 도출 할 수 있다. 그 외의 경우에는 각각의 좌표를 노드라고 생각했을 때, 이 그래프는 각 노드가 노드값이 1만큼 크거나 작은 노드와 2배인 노드와 연결되어 있다. 따라서 BFS를 이용하면 쉽게 해결 할 수 있다. ...