[12851] 숨바꼭질 2

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

숨바꼭질 시리즈이다. 그래프 탐색으로 접근 가능한 문제다. 

 

풀이

실수를 유발하게 하는 포인트가 몇가지 있다. 우선 문제에 동생과 수빈이가 위치한 좌표만 적혀있을 뿐 어디까지 이동이 가능한지 제약이 적혀있지 않다. 즉 동생의 좌표 최댓값 100000보다 더  큰 범위로 순간이동 후 걸어와서 발견하는 방법이 존재한다는 것이다. 역으로 돌아오는 것은 걸어오는 방법(-1) 밖에 없기에 최대 유효 범위는 100001이다. 그보다 큰 위치에서 돌아오는 방법은 최소 시간을 갱신할 수 없다. 따라서 100002개의 배열을 생성한 뒤 한 칸 후퇴, 한 칸 전진, 두배 순간이동의 방법으로 너비 우선 탐색을 수행하면 된다. 

다음으로 중요한 부분은 같은 시간이 걸리더라도 걸어가서 동생을 마주하는 방법과 순간이동으로 마주하는 방법은 다르게 계산해야한다는 점이다. 따라서 도달하게 된 시간이 같다면 도달 방법 수 갱신만 하지 말고 다음 탐색 큐에 담아주어야 한다.

마지막으로 이동하지 않는 것도 방법으로 세야 한다는 것이다. 즉 처음부터 동생과 수빈이의 위치가 같은 경우라면 1을 반환해야 한다.

 

정답 코드

	import Foundation
	let nk = readLine()!.split(separator: " ").map{Int($0)!}
	let n = nk[0]
	let k = nk[1]
	var map = Array(repeating: -1, count: 100002)
	var cnt = 1
	func bfs(from n:Int){
	var q = [n]
	var idx = 0
	while idx < q.count{
	let curr = q[idx]
	let dx = [-1,1,curr]
	let time = map[curr]
	for i in 0..<3{
	let next = curr + dx[i]
	if next<0 || next>=100001 {continue}
	if map[next] == -1{
	map[next] = time+1
	q.append(next)
	if next == k{cnt = 1}
	}else if map[next] > time+1{
	map[next] = time+1
	if next == k{cnt = 1}
	q.append(next)
	}else if map[next] == time+1{
	if next == k{cnt += 1}
	q.append(next)
	}
	}
	idx += 1
	}
	}
	map[n] = 0
	bfs(from: n)
	print(map[k],cnt)

view raw 12851.swift hosted with ❤ by GitHub