전체 글

문제 소개문제 풀이bfs 를 두번 활용하여 구했다. 물이 퍼지는 것을 moveWater() 로 구현했고, 고슴도치가 움직이는 것도 bfs 를 활용하여 구현했다.import Foundation let rc = readLine()!.split(separator: " ").map { Int($0)! } let (r, c) = (rc[0], rc[1]) let ds = [(1, 0), (0, 1), (-1, 0), (0, -1)] var map = [[String]]() var queue: [(Int, Int, Int)] = [] var idx = 0 var widx = 0 var water: [(Int, Int, Int)] = [] var cave = (-1, -1) for i in 0.. time { bre..

문제 소개벽이 움직이는 미로를 탈출하는 문제이다.문제 풀이벽이 아래로 움직이기 때문에 i 와 j 를 바꿔서 배열에 넣어주고 round 마다 +1 을 해주어 갈 수 있는지 없는지를 판별했다.import Foundation let moves = [(1, -1), (1, 0), (0, -1), (0, 0), (-1, 0), (0, 1), (-1, -1), (-1, 1), (1, 1)] var walls = Array(repeating: [Int](), count: 8) for i in 0.. idx { let popped = queue[idx] idx += 1 if popped.0 == 0 && popped.1 == 7 { print(1) exit(0) } if visit.count == popped.2 { ..

Swift에서 스택과 큐Swift로 프로그래밍을 하다 보면 자료구조를 구현해줘야 하는 것들이 있다. 그중 하나가 큐이다. 스택의 경우 removeLast() 와 append(_:) 의 경우 complexity 가 O(1) 이기 때문에 배열에서 위와 같은 함수를 사용하여 그대로 구현할 수 있다.따라서 스택은 구현이랄 것도 없다. 원래 있는 메서드를 개념에 맞게 사용하면 그것이 스택 자료구조이다.var stack: [Int] = [1, 2, 3, 4, 5]stack.append(6)print(stack.removeLast()) // 6print(stack) // [1, 2, 3, 4, 5] 하지만 큐의 경우 FIFO 이기 때문에 removeFirst() 메소드를 사용해야 하는데 문제는 complexity 가..

문제 소개벽 부수기 시리즈! 이번에는 낮에만 블록을 깰 수 있다는 제약조건이 있다.문제 풀이시간 초과와 메모리 초과 때문에 좀 고생을 한 것 같다.시간 초과시간 초과의 경우 의외로 벽을 부시는 경우를 앞쪽에 둬서 해결이 되었다.메모리 초과최대한 요소를 늘리지 않으려고 했다. cost를 2로 나눈 나머지로 낮과 밤을 판별하니 메모리 초과가 나지 않았다. 큐를 구현하지 않고 풀이import Foundation let nmk = readLine()!.split(separator: " ").map { Int($0)! } let (n, m, k) = (nmk[0], nmk[1], nmk[2]) let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)] var..

문제 소개 문제 풀이벽 부수기 4 문제랑 비슷한데 벽을 부수는 횟수가 k 로 주어진다는 차이점이 있다.import Foundation let nmk = readLine()!.split(separator: " ").map { Int($0)! } let (n, m, k) = (nmk[0], nmk[1], nmk[2]) let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() var visited = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: k+1) for _ in 0.. idx { let poped = ..

문제 소개문제 풀이BFS, DFS 두가지 풀이 방법이 있다. 시간은 둘다 22ms, 24ms 로 별 차이 없는 듯 하다.BFSimport Foundation let s = readLine()! let t = readLine()! func bfs() { var queue = [s] var idx = 0 while queue.count > idx { let poped = queue[idx] idx += 1 if poped == t { print(1) exit(0) } if poped.count > 50 { break } if t.contains(poped) || t.contains(String(poped.reversed())) { queue.append(poped + "A") queue.append(Stri..

문제 소개 문제 풀이초기 문제풀이 (시간초과)처음에는 모든 좌표에서 bfs를 통해 갈수있는 칸수를 계산했지만 역시나 시간초과가 났다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() var answer = Array(repeating: Array(repeating: 0, count: m), count: n) for _ in 0.. Int { var queue: [(i: Int, j: Int)] = [(i, j)] var..

문제 소개간단한 bfs 문제이다. 문제 풀이visited 를 3차원 배열로 만들어서 풀었다 왜냐하면 벽을 부순후, 부수기 전의 visited 를 다르게 해줘야 하기 때문이다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) let ds: [(i: Int, j: Int)] = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() var visited = Array(repeating: Array(repeating: Array(repeating: false, count: m), count: n), count: 2) for _ i..