문제 링크
https://www.acmicpc.net/problem/2206
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
문제 풀이
이 문제는 다른 경로 찾기와 비슷하게 기본적으로 BFS(너비 우선 탐색)으로 접근하면 된다. 여기에 하나의 벽을 부술 수 있다는 변수를 어떻게 처리하느냐가 문제 풀이의 핵심이다.
모든 벽을 하나씩 없애보며 경로를 체크하기에는 복잡도가 로 시간이 너무 오래 걸린다. 따라서 아래와 같은 부분을 고려하여 시간을 줄여야 한다.
- 어떤 벽을 부술 경우 최단 경로의 후보에 들어가는지 판별하여 경우의 수를 감소시킨다.
- 벽을 부수는 경우를 포함하여 한 번의 탐색으로 최단 경로를 탐색할 수 있도록 한다.
우선 1번의 경우, 벽 주위의 3면이 벽으로 둘러쌓여 있다면 그 벽은 부수어도 다음으로 진행이 안되어 의미가 없을 것이다. 이를 체크하는 것으로 부수는 경우를 고려하는 벽의 개수를 줄일 수 있을 것이다.
2번의 경우, 핵심은 벽을 부수기 전과 벽을 부순 후를 분리해서 기록하기이다. 한 번의 BFS로 최단 경로를 탐색하기 위해서는 Queue에는 하나의 위치에 대해서 벽을 부순 경우와 부수지 않은 경우의 두 가지 상태를 고려해야 된다. 이 때 단순히 위치로만 이전 방문 목록을 기록한다면, 벽을 부쉈는지의 상태에 따라 달라지는 최단 경로를 제대로 고려하지 못하게 된다. (특히, 벽을 미리 부수면 더 이상 진행하지 못하게 되는 경우에 의해 벽을 부수지 않아 멀게 돌아가던 경로를 덮어씌워 경로를 찾아내지 못하는 경우가 발생한다.) 대표적으로 아래의 반례가 존재한다.
6 6
010001
010101
010101
010101
010110
000110
ans: 21 따라서 이를 해결하기 위해서는 벽을 부순 상태의 위치, 거리를 기록하는 자료구조와 벽을 부수지 않은 상태의 위치, 거리를 기록하는 자료구조 두 개를 이용하여 BFS를 진행해야 한다.
코드 (go)
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
"strings"
)
type Pos struct {
i, j int
}
func (p Pos) neighbors() []Pos {
return []Pos{
{p.i + 1, p.j},
{p.i, p.j + 1},
{p.i - 1, p.j},
{p.i, p.j - 1},
}
}
type Step struct {
Pos
cnt int
broke bool
}
type Queue []Step
func (q *Queue) isEmpty() bool {
return len(*q) == 0
}
func (q *Queue) enqueue(s Step) {
*q = append(*q, s)
}
func (q *Queue) dequeue() (Step, bool) {
if q.isEmpty() {
return Step{}, false
}
s := (*q)[0]
*q = (*q)[1:]
return s, true
}
func printMaze(ll [][]int) {
for _, l := range ll {
fmt.Println(l)
}
fmt.Println()
}
func main() {
reader := bufio.NewReader(os.Stdin)
// Read N, M
line, _ := reader.ReadString('\n')
lineSplit := strings.Split(line[:len(line)-1], " ")
N, _ := strconv.Atoi(lineSplit[0])
M, _ := strconv.Atoi(lineSplit[1])
// Read maze
maze := make([][]int, N)
for i := 0; i < N; i++ {
maze[i] = make([]int, M)
line, _ := reader.ReadString('\n')
for j := 0; j < M; j++ {
x := 0
if line[j] == '1' {
x = 1
}
maze[i][j] = x
}
}
// Find path with BFS
// record dist in maze (negative distance for walls)
queue := Queue{{Pos{0, 0}, 1, false}}
notBrokeHistory := map[Pos]int{{0, 0}: 1}
brokeHistory := map[Pos]int{}
for !queue.isEmpty() {
s, _ := queue.dequeue()
if s.Pos.i == N-1 && s.Pos.j == M-1 {
continue
}
for _, np := range s.neighbors() {
// boundary check
if !((0 <= np.i && np.i < len(maze)) &&
(0 <= np.j && np.j < len(maze[0]))) {
continue
}
// if wall
if maze[np.i][np.j] == 1 {
if beforeCnt, found := brokeHistory[np]; !s.broke &&
isWallWorthBreak(np.i, np.j, maze) &&
(!found || beforeCnt > s.cnt+1) {
brokeHistory[np] = s.cnt + 1
queue.enqueue(Step{Pos{np.i, np.j}, s.cnt + 1, true})
}
} else { // if not wall
var targetHistory map[Pos]int
if s.broke {
targetHistory = brokeHistory
} else {
targetHistory = notBrokeHistory
}
if beforeCnt, found := targetHistory[np]; !found || beforeCnt > s.cnt+1 {
targetHistory[np] = s.cnt + 1
queue.enqueue(Step{Pos{np.i, np.j}, s.cnt + 1, s.broke})
}
}
}
}
brokeResult, brokeFound := brokeHistory[Pos{N - 1, M - 1}]
notBrokeResult, notBrokeFound := notBrokeHistory[Pos{N - 1, M - 1}]
if !brokeFound && !notBrokeFound {
fmt.Println(-1)
} else if brokeFound {
fmt.Println(brokeResult)
} else if notBrokeFound {
fmt.Println(notBrokeResult)
} else {
fmt.Println(int(math.Min(float64(brokeResult), float64(notBrokeResult))))
}
}
func isWallWorthBreak(i, j int, maze [][]int) bool {
// count number of open space around
cnt := 0
if j > 0 && maze[i][j-1] == 0 { // left
cnt++
}
if j < len(maze[i])-1 && maze[i][j+1] == 0 { // right
cnt++
}
if i > 0 && maze[i-1][j] == 0 { // up
cnt++
}
if i < len(maze)-1 && maze[i+1][j] == 0 { // down
cnt++
}
return cnt >= 2
}