dfs32 [Swift][DFS][BFS] 백준 17141번 (연구소 2) 요구능력 : 백트래킹을 통한 BFS 코드설명 : 바이러스가 퍼질 수 있는 위치들이 주어졌다. 이 위치중에서 m개를 골라서 바이러스를 넣고 퍼뜨려야한다. 여기서 바이러스가 퍼질 수 있는 위치(2가 들어 있는 위치)를 먼저 구해서 튜플형태로 배열에 전부 저장해줬다. 그리고 m개를 고르기 위해서 백트래킹을 사용하였다. 백트래킹으로 m개 고른 위치를 bfs에 넣고 bfs로 바이러스를 퍼뜨려준다. check함수를 통해서 벽이아닌데 방문하지않은곳이 있으면 모든 빈칸에 바이러스를 퍼뜨릴 수 없는경우이므로 Int.max를 넣어주고 마지막에도 값이 Int.max라면 결국, 모든 빈칸에 바이러스를 퍼뜨릴 수 없는것이라 -1을 출력해준다. 내 마음대로 설명하는 순열과 조합 순열은 {0, 1, 2, 3}이 있으면 순서를 고려.. 2022. 2. 7. [Swift][DFS] 백준 2580번 (스도쿠) import Foundation var arr = [[Int]]() var col = Array(repeating: Array(repeating: false, count: 10), count: 9) var row = Array(repeating: Array(repeating: false, count: 10), count: 9) var square = Array(repeating: Array(repeating: false, count: 10), count: 9) for i in 0.. 2022. 2. 4. [Swift][Bruteforce] 백준 14225 (부분수열의 합) 요구능력 : 백트래킹 코드설명 : 이 문제는 이 전에 풀었던 부분수열의합(1182번)과 비슷한 느낌의 문제이다. 수열의 경우의수를 백트래킹으로 구하는 부분까지는 같다. 이 문제에서의 핵심 1. 백트래킹 2. 시간초과 안나고 없는수를 어떻게 찾을것이냐.. 처음에는 배열함수써서 인덱스찾고 찾은 인덱스로 지우고.. 뭐 별짓을 다하다가 시간초과가 계속났었다. 시간복잡도에 대해 공부좀해야겠다... 내가 해결한방법은 백트래킹으로 부분수열의 합을 구한다음에 나온 합에대한 부분을 true처리해서 for문을 나올 수 있는 최대합의 경우의수까지 돌리면서 false가 맨 처음 나오면 그게 가장 작은수!라고 풀이를 한것이다. 후기 : 어렵지는 않은 문제인데 결과값범위를 잘못잡아서 헤맸다.. let n = Int(String(.. 2022. 1. 12. [Swift][DFS][LV_2][프로그래머스] 배달 요구능력 : DFS에 대한 이해 코드설명 : 주의: 이 해설은 32번 케이스를 통과하지 못했습니다. DFS로는 도저히 32번을 통과못할것 같지만 풀이가 궁금하신 분들이 계실것같아 올렸습니다. 다음번에 BFS로 풀어보고 따로 글 올리겠습니다. 간선과 가중치가 주어진 문제로 연결그래프를 만들고 그 그래프를 타고가는 방식으로 코드를 짜면된다. 1. 연결그래프 작성 주어진 간선과 가중치를 튜플을 이용해서 연결그래프에 함께 담았다. for i in 0.. k { return } if !visited[i.0]{ visited[i.0] = true count += i.1 if count Int { var visited = Array(repeating: false, count: N + 1) var result = Se.. 2021. 11. 18. 이전 1 2 3 4 5 6 7 8 다음
