[16920] 확장게임

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

16920번: 확장 게임

탐색 종료 조건 부분에서 고생했던 문제였다. 처음에는 지도를 입력받을 때 빈칸의 개수를 세어놓고 빈칸이 0이 될 때까지 플레이어 순서대로 경로탐색을 수행하는 방법으로 시도했으나, 벽으로 둘러싸인 빈 공간의 가능성을 뒤늦게 깨달았다. 

 

풀이

각 플레이어에게 해당하는 경로탐색용 큐 Array(repeating: [[Int]](), count: p+1)를 생성하여 앞으로 방문해야할 공간의 좌표를 담아둔다. 이후 모든 플레이어의 큐가 비어있는 상태가 될 때까지 각 플레이어 턴마다 Si번 경로탐색을 수행하면 된다. 큐의 첫 수행 좌표는 지도를 입력받을 때 큐에 담아두면 된다. 

 

정답 코드

	import Foundation
	let nmp = readLine()!.split(separator: " ").map{Int(String($0))!}
	let n = nmp[0]
	let m = nmp[1]
	let p = nmp[2]
	let s = [0]+readLine()!.split(separator: " ").map{Int(String($0))!}
	var map = Array(repeating: Array(repeating: 0, count: m), count: n)
	var visited = Array(repeating: Array(repeating: false, count: m), count: n)
	var ans = [0]+Array(repeating: 0, count: p)
	var q = Array(repeating: [[Int]](), count: p+1)
	for i in 0..<n{
	let input = readLine()!.map{String($0)}
	for k in 0..<m{
	if input[k]=="#"{
	visited[i][k] = true
	map[i][k] = -1
	}else if input[k]=="."{
	map[i][k] = 0
	}else{
	let number = Int(input[k])!
	map[i][k] = number
	visited[i][k] = true
	q[number].append([i,k])
	ans[number] += 1
	}
	}
	}
	let dx = [-1,1,0,0]
	let dy = [0,0,-1,1]
	func bfs(number:Int){
	for _ in 0..<s[number]{
	if q[number].isEmpty{return}
	var dq = Array(q[number].reversed())
	q[number].removeAll()
	for _ in 0..<dq.count{
	let curr = dq.removeLast()
	let x = curr[0]
	let y = curr[1]
	for i in 0..<4{
	let nx = x+dx[i]
	let ny = y+dy[i]
	if nx<0 || nx>=n || ny<0 || ny>=m || map[nx][ny]<0{ continue }
	if !visited[nx][ny] && map[nx][ny]==0{
	ans[number] += 1
	visited[nx][ny] = true
	map[nx][ny] = number
	q[number].append([nx,ny])
	}
	}
	}
	}
	}
	while true{
	var cnt = 0
	for number in 1...p{
	if !q[number].isEmpty{
	bfs(number: number)
	}
	cnt += q[number].count
	}
	if cnt == 0 { break }
	}
	for i in 1...p{
	print(ans[i],terminator: " ")
	}

view raw 16920.swift hosted with ❤ by GitHub