깊이우선탐색7 [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] 백준 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] 백준 2529번 (부등호) 요구능력 : 백트래킹에 대한 이해 코드설명 : 맨 아래에 수정된 코드있습니다. 이 문제는 0~9까지의 수 중에서 부등호의 갯수 +1 개만큼의 수를 뽑아서 부등호 조건에 맞출 수 있는지를 묻는 문제이다. 문제에서 요구하는 부분 1. 부등호의 개수 + 1개 만큼의 수 2. 뽑은 수를 가지고 부등호 조건을 만족하는지 확인 3. 부등호 조건을 만족하는 수들의 최소값과 최대값 출력 1. 1번부터 해결하면 n과m문제를 떠올리면 된다. 이 문제에서는 0부터 9까지의 수 중에서 선택하라고 했고 선택된 숫자는 모두 달라야한다고 했으므로 방문처리까지 해주면서 방문하는 수를 k + 1 (부등호의 개수 + 1)개 뽑았을 때 부등호조건에 비교하기위해서 result라는 배열에 저장해줬다. for i in 0...9 { if !.. 2021. 11. 8. 이전 1 2 다음
