백트래킹15 [Swift][백트래킹][LV_3] 양과 늑대 요구능력 : 2진트리, 백트래킹 코드설명 : 처음에 배열로 edges를 연결리스트식으로 만들어서 방문했던곳을 다시 들리는(위로다시올라오는) 대참사가 발생했다. dictionary로 아래와 같이 넣으면 한방향(본인 위치의 아래방향)으로 방문하기 편하므로 dictionary를 사용했다. 백트래킹이라고 생각한이유는 모든경우를 다 세어봐야 하기 때문이다. dfs(현재노드, 다음에 방문할 수 있는 노드, 양의 카운트, 늑대의 카운트)로 구성했다. 이렇게 구성한 이유는 양과 늑대의 카운트같은 경우 dfs()함수가 리턴되면 따로 -처리를 해주지 않아도 되기 때문이고(전역으로 선언 시 따로 -처리를 해줘야함), 현재노드 같은 경우에는 시작노드로 0을 전달해줘야 하는것도있고 굳이 0을 전달 안해주고 0으로 시작하더라도 .. 2022. 2. 26. [Swift][프로그래머스][LV_2] 양궁대회 요구능력 : 백트래킹 코드설명 : 문제를 잘 읽어야한다. 핵심적인 부분만 찝어보면 1) k점을 어피치가 a발 맞추고 라이언이 b발 맞췃는데 a >= b이면 어피치가 k점을 가져간다. 2) k점을 여러번 맞혀도 k점만 가져감, a = b = 0인 경우 둘 다 못가져간다. 3) 최종점수가 같을 경우 어피치가 우승자 4) 라이언이 어피치를 가장 큰 점수차이로 이기려고 한다. 5) 라이언이 우승 못하는경우 (지거나 비기는경우) -1리턴 6) 가장 큰 점수차이로 우승할 수 있는 방법이 여러가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 문제의 설명을 읽고 입출력 예를 보고 나서 이 문제가 백트래킹 문제라는 것을 파악했다. 6) 조건을 보면 가장 낮은 점수를 더 많이 맞힌 경우를 return하.. 2022. 2. 22. [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. 이전 1 2 3 4 다음
