전체 글

문제 소개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..

문제 소개https://www.acmicpc.net/problem/2580 스도쿠를 채우는 문제이다. 문제 풀이스도쿠에서 빈칸을 저장한뒤 그 빈칸에 하나하나 입력해주고, 결과가 나오면 exit(0) 를 통해서 값을 내보낸다.import Foundation var sudoku = [[Int]]() var blank = [[Int]]() // 입력 받기 for _ in 0..

문제 소개https://www.acmicpc.net/problem/9663 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 유명한 문제이다. 문제 풀이유명한 문제여서 아주 유명한 풀이가 있다. 이 문제는 사실 어렵지는 않지만 시간복잡도를 최대한 줄이는 것이 관건이라고 할 수 있겠다. 가장 유명한 풀이는 아래와 같다. 한 줄에 무조건 퀸 하나가 들어가야 하기 때문에 한줄한줄 넘어가면서 퀸을 놓는 방식이다. 그리고 colums라는 배열에 쌓아준다. 그리고 퀸을 놓을 때 같은 줄에 있는지, 대각선이라면 x, y 좌표의 차이가 같을 경우인지를 판별한 뒤 넣는다.import Foundation let n = Int(readLine()!)! var colums = Arra..

문제 소개행렬을 뒤집어서 A, B를 같게 만드는 문제이다. 문제 풀이행렬 A, B 를 입력받고 다른 부분을 1로 하는 새로운 diff 행렬을 만든다. 배열을 순회하면서 1이 있으면 행렬을 뒤집는다. 행렬을 뒤집을때마다 count를 세고, 만약 남은 diff 행렬에 1이 남아있을때 -1을 출력하고 diff 행렬이 모두 0이면 count를 출력한다.import Foundation let nm = readLine()!.split(separator: " ").map { Int($0)! } let (n, m) = (nm[0], nm[1]) var a = [[Int]]() var b = [[Int]]() // A, B 행렬 입력 for _ in 0..