[17090] 미로 탈출하기

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

17090번: 미로 탈출하기

그래프 탐색 문제. 시간초과를 해결하지 못해 결국 풀이를 찾아보았다.

---

풀이 방법

배열 범위 밖으로 탈출할 수 있는 노드의 수를 반환해야 한다.

단순히 깊이우선으로 모든 노드에 수행하게 되면 시간초과가 일어난다.

 

미로의 각 칸에서 넘어가는 다음 칸은 지정되어 있다. 따라서 이미 탐색을 수행한 노드의 끝이 맵 밖으로 이어지는지,  아니면 맵을 탈출 하지 못하고 사이클을 형성하는지 미리 저장해 둔다면 시간 내에 정답을 반환할 수 있다.

 

미로와 같은 크기의 N*M 2차원 visited 배열 생성. 특정 좌표를 아직 탐색하지 않았다면 -1, 해당 좌표가 탈출하지 못하는 좌표라면 0, 미로를 탈출할 수 있는 좌표라면 1을 저장한다.

 

깊이 우선 탐색을 수행. 다음 좌표가 미로 밖이라면 1 반환. 아닌 경우에는 처음 방문 좌표인지 확인하여 처음 방문 하는 곳이라면 (-1) 다음 좌표로 재귀호출이 이루어지며 해당 좌표에 결괏값이 저장된다. 

 

탐색을 통해 1의 개수를 정답으로 출력하면 된다.

---

정답 코드

	import Foundation
	let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
	var visited = Array(repeating: Array(repeating: -1, count: M), count: N)
	var map = [[String]]()
	var ans = 0
	for _ in 0..<N{
	let line = readLine()!.map{String($0)}
	map.append(line)
	}
	func dfs(x:Int, y:Int) -> Int{
	var nx = x
	var ny = y
	if map[x][y] == "U"{
	nx -= 1
	}else if map[x][y] == "R"{
	ny += 1
	}else if map[x][y] == "D"{
	nx += 1
	}else if map[x][y] == "L"{
	ny -= 1
	}
	if nx<0 || nx>=N || ny<0 || ny>=M {
	return 1
	}
	if visited[nx][ny] > -1{
	return visited[nx][ny]
	}
	visited[nx][ny] = 0
	visited[nx][ny] = dfs(x: nx, y: ny)
	return visited[nx][ny]
	}
	for i in 0..<N{
	for k in 0..<M{
	if visited[i][k] < 0{
	visited[i][k] = dfs(x: i, y: k)
	}
	ans += visited[i][k]
	}
	}
	print(ans)

view raw 17090.swift hosted with ❤ by GitHub