분류 전체보기

문제 소개 문제 풀이초기 문제풀이 (시간초과)처음에는 모든 좌표에서 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..

문제 소개A, B, C 를 똑같이 만들어 주는 연산이다. 문제 풀이bfs로 풀었다. 어쨋든 똑같은 수로 만들면 되니까... 그리고 var visited = [String: Bool]() 로 visited 를 선언해줬다.import Foundation let abc = readLine()!.split(separator: " ").map { Int($0)! } let (a, b, c) = (abc[0], abc[1], abc[2]) func calc(_ num1: Int, _ num2: Int) -> (Int, Int) { if num1 < num2 { return (num1 + num1, num2 - num1) } else { return (num1 - num2, num2 + num2) } } var qu..

문제 소개https://www.acmicpc.net/problem/14502 연구소에 바이러스가 퍼지지 않게 하는 문제!문제 풀이벽은 dfs를 활용하여 모든 map의 경우를 만들어 준 후, bfs를 활용해서 바이러스를 전파(?)시켜서 최솟값을 구했다. 좀더 구현에 가까운 문제였던듯 싶다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) let ds = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() var queue = [(Int, Int)]() for i in 0.. idx { let poped = queue[idx..

문제 소개문제 자체는 간단하다. DSLR 연산을 통해 a에서 b까지 최소한의 명령어 나열을 출력하는 문제이다. 문제 풀이이 문제는 푸는데는 시간이 많이 걸리지 않았지만 시간 초과로 애를 먹었다. 시간제한이 6초인데 겨우 5880ms 로 통과했다... 다시해봐도 5824ms 가 나오는 것을 봐서는 맞긴 맞은 모양이다... 정답 코드dslr 함수를 구현하고, bfs를 활용했다. L과 R연산을 문자배열을 만들어 하게되면 무조건 시간 초과가 나오게 되어서 연산으로만 구현해줘야 한다. 그리고 처음에는 queue 에 (num, command) 로 넣어주니 이것도 시간초과가 나왔다. 그래서 따로 commands 배열을 만들어 관리해주니 시간 단축이 되었다. queue도 removeFirst() 를 사용하지 않고 id..

문제 소개https://www.acmicpc.net/problem/16928 뱀과 사다리 게임을 하는데 주사위를 굴려야 하는 횟수의 최솟값을 구하는 문제이다. 문제 풀이DFS 를 활용한 풀이board, visited 를 통해 보드의 정보, 방문여부를 저장하여 구현했다. 처음에 틀렸는데 이유는 뱀을 타고 내려가는 경우는 일부로 고려하지 않았는데, 뱀을 타고 내려가는 경우에도 빨리 도착하는 경우가 있다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) var board = Array(repeating: 0, count: 101) var visited = Array(rep..

문제 소개알파벳을 가르칠 수 있고, 아래와 같이 주어질때 6개의 알파벳을 알려줘서 최대로 알수 있는 단어의 개수를 출력하는 문제이다.3 6 antarctica antahellotica antacartica // 2 문제 풀이비트마스크로 해결했다. dfs를 통해 bitmask를 만들고, k만큼 알려줬다면 countReadbleWords 함수를 통해 읽을 수 있는 단어 개수의 최댓값을 출력한다.import Foundation let nk = readLine()!.split(separator: " ").map { Int($0)! } let (n, k) = (nk[0], nk[1]) var words = [Int]() for _ in 0..

문제 소개문제 자체는 아주 간단했다. 아래의 입력값이 주어진다면 알파벳이 중복되지 않게 이동하는 최대 거리를 구하는 문제였다.2 4 CAAB ADCB // 정답 3 문제 풀이초기 문제풀이 (시간초과)우선 최대한 지날 수 있는 칸이기 때문에 dfs를 생각했고, 백트래킹을 통해 문제를 해결하면 된다고 생각했다. 그리고 알파벳을 어떻게 저장할까 고민했는데 Dictionary 나 Set 으로 저장하면 O(1) 으로 알파벳을 방문했는지 빠르게 알 수 있기 때문에 나는 이중에 Dictionary 를 활용했다,import Foundation let rc = readLine()!.split(separator: " ").map { Int($0)! } let (r, c) = (rc[0], rc[1]) let directi..