Algorithm236 [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][BFS] 백준 16954번 (움직이는 미로 탈출) 요구능력 BFS와 level별로 BFS를 확인할 수 있는지 문제풀이 접근법은 뭔가 대놓고 BFS이다. 처음 접근할때 다들 접근법이 가지각색일 것같다. 이 문제는 시간이라는 요소가 정말 중요한 문제이다. 이 문제를 풀기전에 3차원 배열에 대해 간단히 짚고 넘어가야한다. 우선, 3차원 배열은 arr[][][]이렇게 표현하는데 arr[면][행][열]로 보면된다. 이 문제에서는 면은 시간으로 볼것이다. 시간별로 행열의 방문여부를 확인하는 이유는 중복을 없애기 위함이다. 벽의 위치가 같을 때 같은지점을 중복해서 방문하면 시간낭비만 되는 비효율적인 코드가 된다. 벽은 시간에 따라서 움직인다. 따라서 시간에 따라 방문할 수 있는 위치도 초기화해줘야 한다. 그래야 자기자신의 위치에도 중복없이 방문이 가능하다. 나름 중.. 2022. 3. 23. [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. 이전 1 ··· 11 12 13 14 15 16 17 ··· 59 다음
