[Swift 백준] 16173 점프왕 쩰리 (Small)

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")