dfs32 [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][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. [Swift][DFS/BFS] 백준 1260번 (DFS와 BFS) 요구능력: DFS와 BFS 그리고 스택과 큐의 이해 코드설명 : 1. 간선을 받기위함. 이렇게 받으면 a[0]이 시작노드 a[1]이 도착노드인데 서로 넣어준 이유는 간선이 양방향이기때문이다. 예를 들면 간선이 1 5 로 입력되었으면 a[0]가 1이고 a[1]이 5이다. 여기서 a[0]에만 5를 넣어주면 간선은 1->5는 갈수있는데 5->1은 못가는게 된다. 정렬해준 이유는 문제에 순서가 적혀있었기 때문이다. 마찬가지로 둘다 정렬해준 이유는 간선입력이 a[0] = 1, a[1] = 5가 있는데 간선으로 입력받는것중 5로시작하는게 없을경우 정렬이 안되기 때문이다. 2. 시작노드는 시작이기 때문에 당연히 방문처리를 한다. 그리고 방문한 노드를 바로 프린트 해주는 방식으로 했다. DFS는 깊이우선 탐색이기 때문.. 2021. 9. 9. 이전 1 ··· 5 6 7 8 다음