백준177 [Swift][DFS] 백준 13023번 (ABCDE) 요구능력 : DFS와 인접리스트에 대한 이해 코드설명 : 문제를 읽고 예제를 보면 연속적으로 친구와의 관계가 4번 연결되면 정답이된다. 인접리스트를 구하고 인접리스트를 하나씩 DFS하면 된다. 인접리스트와 DFS를 알아야한다. 예제로 인접리스트를 만들어보자. 예제 2번) 5 5 0 1 1 2 2 3 3 0 1 4 인접리스트 0 -> 1, 3 1 -> 0, 2, 4 2 -> 3, 1 3-> 0, 2 4-> 1 인접리스트를 DFS의 노드방식으로 그리고 깊이우선탐색하면 이해가 갈것이다. DFS를 사용하는 이유는 친구와의 관계(depth)를 세기위함이다. 후기 : 처음에 DFS로 4개연속하면 1출력 아니면 0출력이겠다... 까지는 생각했는데, 문제에 대해 이해를 제대로 못했을 때는 인접리스트 수를 세면 되는게 .. 2021. 9. 25. [Swift][DFS][BackTracking] 백준 15650번 (N과 M(2)) 요구능력 : DFS와 백트래킹에 대한 이해 코드설명 : N과 M(1) 에서 "고른 수열은 오름차순 이어야 한다." 라는 조건이 더해졌다. 그럼 우선 수열은 골라놔야하고 그 수열에서 오름차순인지를 판별해서 오름차순인것만 출력하면된다. 그래서 수열이 다 골라지고 print하는 지점에서 배열이 오름차순이면 출력하고 아니면 그냥 리턴하도록 하였다. 후기 : N과M(1) 문제에 간단한 조건1개만 추가한 문제 let arr = readLine()!.split(separator: " ").map{Int(String($0))!} let n = arr[0] let m = arr[1] var visited = Array(repeating: false, count: n + 1) var depth = 0 var result:.. 2021. 9. 25. [Swift][BruteForce] 백준 10974번 (모든 순열) 요구능력 : 순열에 대한 이해 코드설명 : 다음순열을 보고오면 바로 이해가 가능하다. 다음순열의 겉에 팩토리얼로 감싸서 계속해서 순열을 바꿔주고 프린트한게 전부이다. 후기 : 이전에 풀었던 문제중에 다음 순열이 있는데 그 문제를 풀었던 덕분에 쉽게 풀었다. 다음순열에 팩토리얼을 더한 문제 let n = Int(readLine()!)! var sum = 1 var arr: [Int] = [] var result: [Int] = [] factorial(n) for i in 0.. 2021. 9. 24. [Swift][DFS][백트래킹] 백준 15649번 (N과 M (1)) 요구능력 : DFS의 응용 코드설명 : DFS를 활용하는 백트래킹 문제이다. 백트래킹이란? 탐색하는데 필요한 많은 자원을 줄이기 위해 유망성있는 노드들을 중심으로 탐색하는 방법이다. 조건을 줘서 필요없는(유망성없는) 노드에는 방문조차 하지않는다. 백트래킹이라는 방법을 사용하기위해 DFS를 이용한다고 생각하면 된다. 이 문제에서 핵심 두 가지다. 1. 수열을 만들되, 백트래킹을 이용하여 중복되는 수(유망성없는 수)를 방문하지 않는다는것이다. 2. DFS를 사용하기 때문에 Stack을 활용한다는 것이다. 문제예시) 4 4를 입력했다고 치자. 아래 코드를 실행하게 되면, result(0) depth = 0, visitied[1] = false -> visited[1] = true, stack = [1] res.. 2021. 9. 23. 이전 1 ··· 26 27 28 29 30 31 32 ··· 45 다음