[BOJ] 백준 14940 쉬운 최단거리 (Swift)

문제

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

 

풀이

BFS로 쉽게 풀 수 있는 문제이다.
다만 문제에 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 라는 문장이 있어
BFS를 한번 돌리고 난 이후 검사를 해서, 갈 수 있는 땅인데 도달하지 못했다면 -1로 변경시켜주는 과정을 거쳤다.

소스코드

	let dy = [1, 0, -1, 0]
	let dx = [0, 1, 0 ,-1]
	let input = readLine()!.split { $0 == " " }.map { Int($0)! }
	let n = input[0], m = input[1]
	var graph: [[Int]] = []
	var visited = [[Bool]](repeating: [Bool](repeating: false, count: m), count: n)
	for _ in 0..<n { graph.append(readLine()!.split { $0 == " " }.map { Int($0)! }) }
	var start = (0, 0)
	for y in 0..<n {
	for x in 0..<m {
	if graph[y][x] == 2 {
	start = (y, x)
	break
	}
	}
	}
	var queue = [(start.0, start.1, 0)]
	var index = 0
	var answer = [[Int]](repeating: [Int](repeating: 0, count: m), count: n)
	while queue.count > index {
	let y = queue[index].0
	let x = queue[index].1
	let d = queue[index].2
	visited[y][x] = true
	answer[y][x] = d
	for i in 0..<4 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if 0..<n ~= ny && 0..<m ~= nx && !visited[ny][nx] && graph[ny][nx] != 0 {
	visited[ny][nx] = true
	queue.append((ny, nx, d + 1))
	}
	}
	index += 1
	}
	for y in 0..<n {
	for x in 0..<m {
	if graph[y][x] == 1 && answer[y][x] == 0 {
	answer[y][x] = -1
	}
	}
	}
	answer.forEach {
	print($0.map { String($0) }.joined(separator: " "))
	}

view raw 쉬운 최단거리.swift hosted with ❤ by GitHub

후기

기본적인 BFS 문제였다.