Baekjoon78 [Swift][BFS] 백준 1697번 (숨바꼭질) 요구능력 : BFS에 대한 이해 코드설명 : 왜 BFS로 풀어야되는지에 대한 설명이 아주 잘나와있다.https://chanhuiseok.github.io/posts/baek-14/ [백준] 1697번 - 숨바꼭질 컴퓨터/IT/알고리즘 정리 블로그 chanhuiseok.github.io 스위프트의 경우에는 큐를 구현해줘야하기 때문에 필요한 부분만 구현해줬다. BFS의 경우 처음에 큐가 비어있기 때문에 큐에 입력받은 수를 푸쉬해준다. 그리고 큐에서 데이터를 하나 꺼내오고 꺼내온 데이터가 k와 같다면 while문을 빠져나가준다. while문의 조건을 true로 놔둬도 상관없다. 문제풀이이기 때문에, data가 k와 같지않은 경우는 없기때문이다. 아래의 세 가지 경우를 모두 돌면서 1) x - 1 2) x + .. 2021. 9. 27. [Swift][DFS] 백준 11724번 (연결 요소의 개수) 요구능력 : DFS와 인접리스트에 대한 이해 코드설명 : 평범한 DFS문제처럼 인접리스트를 구해준다. 문제에서 따로 함수를 빠져나갈 조건이 나오지 않았으므로 사실 depth도 필요는 없다. 그냥적은거다. 조건이 없으니 방문처리만하고 나가는 처리는 할필요가 없다. 여기서 핵심은 인접리스트를 다 돌면서 이미 방문한 노드들은 돌지않고 돌게되는 인접리스트는 카운트를 해주는 것이다. 이미 방문한 노드들은 한개의 묶음의 노드이기 때문이다. (하나의 연결요소이기 때문이다.) DFS는 같은 묶음에 있는 노드는 다 돌게 되어있다. 그러니 방문하지 않은 노드는 다른 연결요소라는 뜻이다. 후기 : DFS문제는 아직 어렵다 .. 적응이 좀 더 필요하다.. let arr = readLine()!.split(separator: .. 2021. 9. 26. [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. 이전 1 2 3 4 5 6 7 ··· 20 다음