backtracking
-
백준 17070 파이프 옮기기 1Algorithm/BOJ 2021. 4. 20. 12:38
출처: www.acmicpc.net/problem/17070 분류: DP, 백트래킹 접근방식 주어진 요구사항 대로 파이프의 이동 가능 위치를 잘 계산하고 나면 백트래킹으로 도착한 경우의 수를 세주면 되는 문제였습니다. 파이프의 끝 점에서 출발한 경로는 역시 다시 방문해줄 필요가 없으므로 방향을 고려한 3차원 배열에 이를 기록해서 방문 횟수를 줄여줬습니다. 조금 귀찮긴 하지만 크게 어렵지는 않아서 풀이를 보시면 이해가 되실거에요 :) 해결방법 let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Direction { if pipe.0.r == pipe.1.r, abs(pipe.0.c - pipe.1.c) == 1 { return .horizontal } ..
-
백준 1759 암호만들기Algorithm/BOJ 2021. 2. 2. 12:08
출처: https://www.acmicpc.net/problem/1759 분류: 백트래킹 접근방식 백트래킹 방식으로 풀어봤습니다. 완성한 암호가 모음 1개 자음 2개 이상인지 확인해야 하는 것만 주의하면 어렵지 않게 풀 수 있을 것 같네요! 체크하는 건 모음 set을 만들어두고 완성된 문자열과 교집합을 구해서 카운트하는 방식으로 풀어봤습니다 :) 해결방법 let lc = readLine()!.split(separator: " ").map { Int($0)! } var alphabets = readLine()!.split(separator: " ").sorted() var available = [Bool](repeating: true, count: lc[1]) var predicted: String = "..
-
백준 15649 N과 M(1)Algorithm/BOJ 2021. 1. 28. 11:29
출처: https://www.acmicpc.net/problem/15649 분류: 백트래킹 접근방식 1~N까지의 수 중에서 중복없이 해당 길이의 모든 경우의 수를 다 찾는 문제였습니다. 가능한 모든 경우의 수를 다 고려하는 백트래킹으로 해결했습니다. 처음엔 원하는 길이만큼 만들어 나가는 dfs를 1~N을 시작점으로 해서 여러 번 돌리는 방식으로 풀었는데요 백트래킹을 공부하고 정통적인 방법으로 다시 풀어봤습니다. 해결방법 1 ~ N을 시작으로 해서 주어진 길이만큼의 배열을 만들어나가는 dfs 방식입니다. protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } exten..