DFS
-
백준 1937 욕심쟁이 판다Algorithm/BOJ 2021. 4. 19. 19:39
출처: www.acmicpc.net/problem/1937 분류: DP, DFS 접근방식 기본적인 DFS 접근 방식에 DP의 개념을 추가해서 풀 수 있는 문제였습니다. 한 점에서 갈 수 있는 최대 거리(판다의 생존 일 수)를 DFS를 통해 구해나가는 데, 어차피 그 점에서 시작한 결과는 어차피 어디서 와서 시작하든 같기 때문에 다시 탐색할 필요가 없다는 점을 이용합니다. 따라서 일 수를 기록하는 Map크기와 같은 DP를 채워나가면 해결할 수 있었습니다. 해결방법 import Foundation typealias Point = (r: Int, c: Int) let n = Int(readLine()!)! var map = [[Int]]() for _ in 0.. Int { guard dpMap[curr.r]..
-
백준 1520 내리막 길Algorithm/BOJ 2021. 3. 30. 14:00
출처: www.acmicpc.net/problem/1520 분류: DP, DFS 접근방식 DFS 방식으로 원하는 칸에 도달하는 경로를 찾아나갈 수 있습니다. 대신 모든 경우를 탐색하면 시간제한에 걸리게 되므로 DP를 활용해야 합니다. 현재 칸에서 가능한 경우의 수는 이미 모두 탐색을 했기 때문에 방문한 칸을 다시 방문할 필요는 없고 저장된 방문 횟수만 가져옵니다. 구체적으로는 처음에 DP 배열에 -1을 넣어두고 방문하면 0으로 초기화하고 값을 더해줍니다. DP가 -1일 경우에만 탐색하고 아니면 DP의 값만 리턴합니다. 해결방법 typealias Point = (r: Int, c: Int) let rc = readLine()!.split(separator: " ").map { Int(String($0))!..
-
백준 2210 숫자판 점프Algorithm/BOJ 2021. 3. 29. 14:34
출처: www.acmicpc.net/problem/2210 분류: dfs, 완전탐색 접근방식 왔던 칸을 다시 가도 되므로 그냥 보드의 범위를 넘지 않는지만 체크하면서 6자리까지 dfs 로 계속 숫자를 더해주고 set에 담아서 개수를 출력하면 되는 문제였습니다. 저는 다음 칸을 만들고 filter로 범위를 걸러주는 식으로 풀어서 먼저 범위를 체크하고 만드는 것보다 시간이 좀 더 걸린 것 같네요! 해결방법 typealias Point = (r: Int, c: Int) var board = [[String]]() var digitSet = Set() for _ in 0.. [Point] { return [ (p.r+1, p.c), (p.r-1, p.c), (p.r, p.c+1), (p.r, p.c-1) ].f..
-
백준 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..
-
백준 3019 빵집Algorithm/BOJ 2020. 6. 18. 15:35
출처: www.acmicpc.net/problem/3109 분류: 그리디, DFS 접근방식 첫번째 열부터 차례대로 연결할 수 있는지 탐색하면 되는 문제입니다. 처음에 그냥 풀었다가 시간초과가 나고.. dfs를 사용해서 풀었는데, 주의할 건, 다음으로 연결할 수 있는 경우는 오른쪽, 오른쪽 위, 오른쪽 아래 3가지라서 다음 경우까지 모두 해봐야 하기 때문에 dfs에서 결과를 그냥 리턴하면 안되고 true일 경우에만 리턴해야 합니다. 해결방법 let n = readLine()!.split(separator: " ").map{Int($0)!} var map = [[Bool]]() for _ in 0.. Bool { return r >= 0 && c >= 0 && r < n[0] && c < n[1] } var..
-
Algorithm) BOJ) 백준 7576 - 섬의 개수Algorithm/BOJ 2019. 6. 6. 11:13
문제보러가기 1. 초기접근 문제 조건 해석 전형적인 dfs 문제로 단지번호붙이기 문제와 유사하다. 단, 이번에는 동서남북 + 대각선 까지 구해야 한다. 알고리즘 w, h 크기의 섬을 돌면서 dfs탐색을 한다. 섬의 개수만 구하면 되므로 처음 dfs를 시작할 때마다 count를 늘려준다. 2. 회고 전형적인 dfs문제였다. 머리속에 그려지는 문제는 빠르고 정확하게 풀 수 있도록 노력하자. 3. 코드 while let testCase = readLine()?.split(separator: " ") { let w = Int(testCase[0])! let h = Int(testCase[1])! if w == 0 && h == 0 { break } var map = [[String]](repeating: [St..
-
Algorithm) BOJ) 백준 2667 - 단지번호붙이기Algorithm/BOJ 2019. 6. 6. 00:42
문제보러가기 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 1. 초기접근 문제 조건 해석 전형적인 DFS 문제이다. (0,0) ~ (n, n) 까지 돌면서 방문하지 않은 곳은 단지를 이룬다. 알고리즘 (0,0) ~ (n,n) 까지 돌면서 아직 방문하지 않았고, 1인 곳에서 d..