BFS
-
백준 1261 알고스팟Algorithm/BOJ 2021. 6. 14. 15:41
출처: https://www.acmicpc.net/problem/1261 분류: BFS, 다익스트라 접근방식 0은 그냥 통과, 1이 있는 칸은 벽을 부수면서 목적지까지 갈 때 최소한 몇 개의 벽을 부숴야하는지 찾는 문제였습니다. dist 배열을 두고 최소 비용을 갱신해주면서 BFS 탐색을 해주는 방식으로 해결했습니다. 해결방법 let mn = readLine()!.split(separator: " ").map { Int(String($0))! } let (m, n) = (mn[0], mn[1]) let delta = [(1, 0), (-1, 0), (0, 1), (0, -1)] var map = [[Int]]() for _ in 0..= 0, nr = 0, nc < m else { con..
-
Programmers Lv3) [2020 카카오 인턴십] 경주로 건설Algorithm/Programmers 2021. 4. 21. 17:16
출처: programmers.co.kr/learn/courses/30/lessons/67259 분류: Lv3, BFS 접근방식 BFS 방식으로 해결했습니다. 조금 확장된 개념이 들어가는데, 단순히 방문 체크에 더해서 비용과 방향까지 기록해주면서 탐색해나가면 됩니다. 방향까지 체크해주는 이유는 같은 가격이여도 어떤 방향에서 오는지에 따라 달라질 수 있기 때문입니다. 현제 체크되어 있는 방향의 비용보다 더 작다면 다시 방문해주는 방식이 되겠습니다. 저는 enum으로 방향을 정의해주고 (그냥 Int나 bool 변수 등으로 정의해도 상관없을 것 같습니다.) Point 를 하나 정의해서 가지고 있도록 해줬습니다. enum Direction: Int { case horizontal = 0, vertical } ty..
-
백준 16920 확장 게임Algorithm/BOJ 2021. 4. 9. 14:42
출처: www.acmicpc.net/problem/16920 분류: BFS 접근방식 문제 자체도 복잡하긴 한데 문제 설명이 좀 애매해서!!!!! 애를 좀 먹었던 문제였습니다. Si칸 만큼 이동할 수 있는 모든 칸에 성을 동시에 만든다. 문제를 보면 위와같이 써있는데요, 이렇게 되면 딱 Si 번째 칸만 칠하는 것(성으로 만드는 것)처럼 생각할 수 있는데 그게 아니라 Si번까지 이동하는 중에 있는 칸은 모두 칠해야 합니다. 반례는 예제 6번에 있는데요, 예제 6번을 살펴보면 처음 플레이어1 이 플레이 하고나면 ["1", "1", "1", "1"] ["1", "1", "1", "1"] [".", "1", "1", "."] ["1", ".", ".", "2"] 다음과 같이 되고 그 다음에 플레이어2 가 진행하고..
-
백준 16234 인구 이동Algorithm/BOJ 2021. 4. 8. 11:46
출처: www.acmicpc.net/problem/16234 분류: BFS, DFS 접근방식 BFS 또는 DFS로 해결할 수 있는 문제였습니다. 주어진 범위에 해당하는 칸들을 탐색하고 그룹짓고를 반복하면 됩니다. 저는 BFS를 사용했는데요, 탐색하면서 멤버들의 따로 저장해뒀다가 탐색이 끝나기 전에 tempMap에 결과를 기록해두고 전체를 다 돌고 temp와 map을 비교해서 다시 해야할지 말지를 결정해주면서 카운트했습니다. 해결방법 struct Point { var r: Int var c: Int init(_ r: Int, _ c: Int) { self.r = r self.c = c } var nexts: [Point] { return [ Point(r+1, c), Point(r-1, c), Point(..
-
백준 13549 숨바꼭질 3Algorithm/BOJ 2021. 4. 7. 11:20
출처: www.acmicpc.net/problem/13549 분류: BFS, Deque 접근방식 현재 위치에서 이동할 수 있는 위치를 담으면서 BFS 탐색을 해서 해결할 수 있습니다. 단, 그냥 앞뒤 이동 보다 jump가 비용이 더 적게 들기 때문에 jump를 우선적으로 처리해줘야 합니다. 이때 사용할 수 있는 방법은 여러가지인 것 같은데요, 저는 jump는 queue의 앞에 추가하고 나머지는 뒤에 추가하는 방식으로 jump를 우선적으로 처리해줬습니다. 시간은 널널해서 그냥 배열로도 처리할 수 있는데, deque를 사용하면 효율을 훨씬 높일 수 있습니다. 해결방법 그냥 배열 let nk = readLine()!.split(separator: " ").map { Int(String($0))! } var v..
-
백준 1981 배열에서 이동Algorithm/BOJ 2021. 4. 1. 21:05
출처: www.acmicpc.net/problem/1981 분류: 이분탐색 접근방식 이 문제는 n이 최대 100으로 100 x 100 배열이기 때문에 단순 무식하게 BFS 접근하면 시간초과를 맞게 됩니다. 어떻게 하면 방문을 범위를 제한할 수 있을까요? 이 문제에서도 이분탐색의 아이디어를 적용해볼 수 있습니다. 우선 차이가 가장 작아지는 경우는 언제일까요? 경로의 최대최소가 같은 경우면 차이가 최소가 될 수 있겠죠? 때문에 최소는 언제나 가능성이 있으니 0으로 둡니다. 그럼 차이가 최대가 될 때는 언제일까요? 배열에 나오는 최대값과 최소값이 모두 들어있을 때, 즉 최대 - 최소가 차이의 최대가 되겠네요. 저희는 최소를 구해야 하기 때문에 만약 0 ~ 8 까지 가능성이 있을 때, 차이를 4로해서 가는 경우..
-
백준 17142 연구소 3Algorithm/BOJ 2021. 3. 17. 16:09
출처: www.acmicpc.net/problem/17142 분류: 완전탐색, BFS, DFS 접근방식 조합과 BFS를 사용해 해결할 수는 문제였습니다. 바이러스가 활성화될 수 있는 지역과 최대 활성화시킬 수 있는 바이러스의 수가 주어졌을 때, 활성화 바이러스의 조합을 뽑아 BFS를 돌려 최단 거리를 계산합니다. 활성화 바이러스의 조합은 순서 상관없이 뽑는 경우의 수이기 때문에 순열이 아닌 조합으로 처리해줘야 합니다! var selected = [Point]() func selectVirus(curr: Int) { if selected.count == nm[1] { let time = infectTime(selected) if time != -1 { if minimumTime == -1 { minimum..
-
백준 16236 아기상어Algorithm/BOJ 2021. 3. 10. 18:08
출처: www.acmicpc.net/problem/16236 분류: BFS 접근방식 상어가 먹이를 찾을 수 없을 때가지 최단거리의 먹이를 찾아 bfs를 돌려주면 되는 문제였습니다. 기술적으로 크게 어려운 것은 없었으나... 익숙하지 않다면 구현에서 좀 애를 먹을 수 있을 것 같네요..! (후 힘들었습니다..) 같은 거리의 먹이들이 여러 개라면 요구사항대로 정렬을 해줘야 합니다! row 우선, 그다음 col로 ..! feeds.sorted(by: { $0.r == $1.r ? $0.c < $1.c : $0.r < $1.r}) 큐에서 DoubleStackQueue를 사용했는데 그냥 배열로 해서 removeFirst해도 통과가 가능한 것 같습니다. 해결방법 struct DoubleStackQueue { pri..