dfs32 [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] 백준 18290번 (NM과 K(1)) 요구능력 : DFS 코드설명 : DFS문제이지만, 마냥 순열로 풀어버리면 DFS에 O(n^2)이 나와버려서 통과가 안된다. 그래서 처음에는 선택으로 가려고 x와 y둘다 이전에 방문했던 부분 다음 부분부터 방문하게했더니 , 그렇게 하면 탐색하는 줄이 다음줄로 넘어가도 y좌표도 이전에 방문했던 부분의 다음부분부터 방문해버리는 문제가 생겨서 x만 중복을 최대한 줄이는 쪽으로 문제를 해결했다. 이거 외에 이 문제에서 핵심이라고 볼만한것은 바로 이 부분이다. func check(_ x: Int, _ y: Int) -> Bool{ for i in 0..= n || ny = m{ continue } if visited[nx][ny] { //현재 좌표와 인접한 곳이 이전에 방문한적 있었다면 현재좌표.. 2022. 2. 17. [Swift][DFS][BFS] 백준 17142 (연구소 3) 요구능력 : 백트래킹과 BFS 코드설명 : 연구소 2 문제를 안풀었다면 먼저 풀고오는게 맞는거같다. 연구소2 문제와 다른점만 설명하고 넘어가겠다. 연구소2 같은경우에는 선택되지 않은 바이러스는 그냥 빈칸처럼 사용했다. 연구소3 에서는 비활성바이러스를 활성바이러스로 바꾸기위해서 해당 바이러스를 활성화해서 큐에 넣어야한다. 그런데 어려워보이고 정답비율이 낮은이유가 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다." 위 설명 때문이다. 말이 어렵지 그냥 빈칸없으면 정답이된다. 왜? 핵심적으로 봐야될 부분은 "활성바이러스가 비활성 바이러스가 있는 칸으로 간다."는 것이다. 그럼 활성바이러스가 비활성바이러스로 갈 때는 결국 세줘야한다. 빈칸처럼 쓰는거랑 그럼 차이점이 뭐냐?.. 2022. 2. 11. 이전 1 2 3 4 5 6 ··· 8 다음
