[BOJ] 백준 2206 벽 부수고 이동하기 (Swift)

문제

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

2206번: 벽 부수고 이동하기

풀이

BFS로 풀이할 수 있는 문제입니다.
벽을 한 번도 안부수고 이동하는 것과, 한 번 부수고 이동하는 것을 나누어서 생각해야합니다.

벽을 부시고 그 좌표를 방문했는지, 한 번도 안부수고 방문했는지를 나타내기 위해 3차원 Bool 배열을 사용하였습니다.

벽을 안부셨다면 다음 이동할 좌표가 0이면 그냥 방문하면되고, 1이라면 벽을 부시고 방문할 수 있습니다.
벽을 한 번 부셨다면 다음 이동할 좌표가 0이면 방문할 수 있지만, 1이라면 방문할 수 없습니다.

BFS 함수안에서 이 두 경우를 나누어서 최단 거리를 알 수 있습니다.

소스코드

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

view raw 벽 부수고 이동하기.swift hosted with ❤ by GitHub

후기

벽을 부순 여부를 알기 위해 3차원 배열을 떠올려서 풀었던 문제였습니다.