Algorithm
[Swift 백준] 16173 점프왕 쩰리 (Small)
Kim Roks
2025. 3. 5. 22:32
https://www.acmicpc.net/problem/16173
풀이 아이디어
그래프 탐색 문제입니다
bfs를 선호하지만 연습을 위해 재귀를 활용한 dfs로 풀이했습니다.
두 방향으로만 이동가능하며 그래프를 넘어가면 즉시 종료시켰습니다.
풀이
import Foundation
let n = Int(readLine()!)!
var graph = [[Int]]()
for _ in 0..<n {
graph.append(readLine()!.split(separator: " ").map { Int($0)! })
}
var visited = Array(repeating: Array(repeating: false, count: n), count: n)
let dx = [0, 1]
let dy = [1, 0]
func dfs(_ x: Int, _ y: Int) -> Bool {
if x < 0 || y < 0 || x >= n || y >= n || visited[x][y] {
return false
}
if graph[x][y] == -1 {
return true
}
visited[x][y] = true
let jump = graph[x][y]
for i in 0..<2 {
let nx = x + dx[i] * jump
let ny = y + dy[i] * jump
if dfs(nx, ny) {
return true
}
}
return false
}
print(dfs(0, 0) ? "HaruHaru" : "Hing")