백준 - 16173 swift
문제
아이디어
일단 이 문제를 이해하는데만 오래 걸려서 시간내에 풀지 못했다. 계속 붙들고 있는 것보다 다른 블로그를 참고하는게 효율적이라는 생각이 들어 블로그를 참고하였다.
내가 이해한 부분 & 접근방법
처음에 입력받을 때 게임 구역의 크기가 2와 3으로 한정된다고 한다. 그럼 만들어질 수 있는 게임 구역은 최소 4칸 최대 9칸을 가진 정사각형으로 이루어진다.
그럼 이차원배열을 사용해서 한 번에 이동할 수 있는 칸의수를 맨 오른쪽 아래 칸에 도달할 수 있는지 없는지를 판단하면 되지 않을까? 라는 생각이 들었다.
문제는 구현을 못하겠다는 것이다;ㅋㅋ
그래서 몇가지의 블로그를 참고 해보니 백준 16173문제는 전형적인 탐색 알고리즘을 사용해서 푸는 문제이며, DFS와 BFS를 사용해서 간단하게 풀 수 있다고 한다.
알고리즘인지 자료구조 시간에 배웠는데, 복습 겸 해당 알고리즘을 사용하여 코드를 구현해보자.
DFS(깊이 우선 탐색)
- 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식
- 탐색 노드의 인접 노드의 자식 노드들을 모두 탐색하고 탐색 노드의 다른 인접 노드 자식들을 모두 탐색하는 방법이다.
- DFS는 왼쪽을 먼저 탐색하냐, 오른쪽을 먼저 탐색하냐 같은 순서는 중요하지 않으며 어디를 먼저 탐색하더라도, 해당 노드의 가장 깊은 노드까지 우선 다 탐색해야 다음 인접 노드를 탐색할 수 있다.
BFS(너비 우선 탐색)
- 인접한 노드들을 우선 탐색하는 방식
- BFS 또한 왼쪽을 먼저 탐색하냐, 오른쪽을 먼저 탐색하냐의 순서는 중요하지 않으며 같은 레벨에 있는 노드를 먼저 다 탐색해야 다음 레벨 노드를 탐색할 수 있다.
둘 다 시간 복잡도는 동일하지만, 실제 수행시간은 BFS가 조금 더 빠르다.
코드
import Foundation
let n = Int(readLine()!)! //게임 구역의 크기(2와 3으로 한정)
var map = [[Int]]()
for _ in 0..<n {
let map_size = readLine()!.split(separator: " ").map {Int($0)!} //게임 구역의 크기 만큼 mapsize 입력받기
map.append(map_size)
}
var start = (0, 0)
var visited = [[Bool]](repeating: [Bool](repeating: false, count:n), count:n)
func dfs(_ x: Int,_ y: Int) { //구역의 크기가 2랑 3으로 밖에 제한적이지 않으니까 dfs사용함.
visited[x][y] = true
let dx = [map[x][y], 0]
let dy = [0, map[x][y]]
for i in 0..<2 {//최대가 3까지니까
let nx = x + dx[i]
let ny = y + dy[i]
if (0 <= nx && nx < n) && (0 <= ny && ny < n) && !visited[nx][ny] { //nx와 ny가 (0,0)보다 크고 오른쪽 맨 아래 칸에 도달하지 않았을 경우 dfs함수를 실행해라.
dfs(nx, ny)
}
}
}
dfs(0,0)
if visited[n-1][n-1] {
print("HaruHaru")
} else {
print("Hing")
}
다른 블로그를 보니 수행시간 때문에 BFS로 많이 풀었던데 이번 문제는 게임블럭의 사이즈가 최대 9이기 때문에 DFS 알고리즘을 사용하도록 하였다. (물론 블로그를 참고 했지만...)
해당 코드는 그래프의 크기를 결정하는 정수 n을 입력받고, 맵 크기를 나타내기 위해 빈 배열 map을 초기화 한다.
n x n 크기의 2차원 bool 배열로 방문한 지점을 추적하기 위해 사용되는 visited배열을 초기화 해주었다. 처음에는 모든 원소가 false로 초기화되며, dfs함수 내에서 현재 위치를 방문했으면 true로 값을 바뀌게 한다.
현재 위치에서 이동 가능한 방향을 나타내는 dx와 dy 배열을 설정하여 이동가능한 방향에 대한 반복문을 실행하고 각 방향에 대한 nx와 ny를 계산한다.
visited배열의 마지막 원소에 true가 설정되어 있다면, "HaruHaru"를 출력하고 그렇지 않으면 "Hing"을 출력하도록 한다.
참고한 블로그 중에서 swift로 작성된 블로그가 없길래, 파이썬으로 작성된 블로그를 swift로 바꾸어 풀었다.
swift문법에 대해서 익숙하지 않다보니 2차원 배열을 어떻게 사용하는지, 한줄에 여러 정수를 입력했을 때 띄어쓰기로 어떻게 구분하는지에 대한 것들을 찾아보면서 하다보니 더 오래 걸린거 같다.
같은 swift라도 프로젝트 하는거랑 코테랑 너무 다른거 같다 . .(아직 너무 부족해서 공부할게 너무 많다 ㅎㅎ..)