백준177 [Swift][BFS] 백준 16940번 (BFS 스페셜 저지) 요구능력 BFS와 정렬 문제설명 일반적인 BFS문제에 주어진 방문순서대로 방문이 가능한지를 판별하는 문제이다. 간선정보가 주어진다면 인접리스트를 고려해봐야한다. 그래서 인접리스트를 구현했고, 이 인접리스트에 따라서 BFS탐색을 해준다. 1부터 시작한다고 했으므로 1부터 시작해주고 result에는 BFS탐색순서대로 탐색하는 노드들을 저장한다. 우리는 주어진 BFS의 방문순서가 가능한것인지 아닌지를 판별해야한다. 그렇기 때문에 주어진 BFS의 방문순서대로 방문을 해보고 되면 1을 출력하고 안되면 0을 출력해야한다. 그래서 주어진 BFS의 방문순서대로 우선순위를 부여해서 먼저 방문해야하는 노드가 있다면 먼저 방문해줘야한다. 우선순위의 경우 0이아닌 1부터 저장하기위해서 i + 1로 해준것이고 i로해도 딱히 상.. 2022. 3. 26. [Swift][Graph] 백준 12946번 (육각보드) 요구능력 DFS 활용 문제풀이 이분의 블로그를 참고하였다. https://astrid-dm.tistory.com/380 백준 12946번 육각 보드 (C++) 문제 링크 : www.acmicpc.net/problem/12946 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을.. astrid-dm.tistory.com 후기 여섯방향으로 탐색해야하고 최대 3개의 색상밖에 안나온다는 것까지는 파악하기 쉬웠는데, 몇가지 예외가 생기는거 같아서 탐색의 갈피를 못잡았다. 코드 import Foundation let n = Int(String(readLine()!))! var arr .. 2022. 3. 22. [Swift][BruteForce] 백준 14391번 (종이 조각) 요구 능력 BruteForce + recursiveFunction(DFS) 문제설명 가로와 세로를 섞어서 찢는데 나올 수 있는 가장 큰 수를 구하는 문제이다. 시간복잡도 종이조각을 가로로 자르거나 세로로 자르는 2가지의 경우가 모든칸에 적용될 수 있으므로 O(2^n)의 시간복잡도를 갖는다. n과 m이 최대4까지 나오니까 2^16이 최악의경우이다. 그리고 가로 혹은 세로로 찢어지는 경우마다 우리는 완전탐색을 해서 한번씩 들여다봐야하기 때문에 O(n *m)의 시간복잡도가 걸린다. 종합적으로 O(2^n * m * n)의 시간복잡도가 걸리는것이다. DFS() 처음에는 이게 무슨뜻이지 싶었는데, 방문처리가 true로 처리됬을 경우에는 가로로 찢어진것을 의미하고, 방문처리가 false로 처리됬을 경우에는 세로로 찢.. 2022. 3. 22. [Swift][DFS] 백준 1248번 (맞춰봐) 요구능력 : DFS 재귀 코드설명 : 일단 문제를 이해해야하는데,, 예제입력 1에 적혀있는 -+0++++--+로 예를 들어 설명해보자. 규현이가 쓴 수가 A[]라는 배열에 4개가 저장되어 있다고 가정해보면 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합이 음수, 양수, 0으로 구분되어 저장되는 것이라고 보면된다. 예제 출력1처럼 -2 5 -3 1일 때 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합을 직접해보면 -+0+가 나오는걸 알 수 있다. 이후에도 A[1]의 합, A[1] ~ A[2]의 합, ... 이렇게 구해보면 문제에서 뭘 구해야하는지 이해가 갈것이다. 나는 처음에 result배열에 그냥 평범.. 2022. 3. 15. 이전 1 ··· 5 6 7 8 9 10 11 ··· 45 다음
