[백준 / BOJ] 2206 벽 부수고 이동하기

문제

출처 : www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

N*M행렬이 주어진다. 이때, 이동할수있는곳은 0 벽이있어서 이동할수 없는곳은 1로 표시된다. 

이동할때 벽을 최대 1회 부수고 이동할수있는데, 1,1에서 시작해서 N,M에 도달했을때 최단경로를 구하는 문제다.

 

풀이

BFS문제다.

일반적인 BFS와 check배열을 선언하는게 다른데, 3차원 체크배열을 선언해서 해당 지점에 벽을 부수고 이동한 경로와 최솟값과 벽을 부수지 않고 이동한 경로의 최솟값을 저장해줘야한다.

 

check[Y][X][벽을부수는 기회를 사용했나 안했나] = 이동횟수

3차원배열의 벽부수는 기회를 0,1로 나타내준다 했을때,

check[Y][X][0] = 벽을 부술기회가 남아있는 상태로 Y,X로 이동함.

check[Y][X][1] = 벽을 부술기회를 이전에 사용한상태로 Y,X로 이동함.

 

예를들어,

N = 4, M = 4

0000

1 1 1 1

0010

0010

이런식으로 주어졌을때,

(4,4) 에 최소한으로 이동하는 경우는

check[1][1][0] (1,1) -> 오른쪽으로 3번이동 -> check[1][1][0] (1,4) -> 벽부수고 아래로 3번이동(이때부터 check[Y][X][1]로 저장해준다.) -> (4,4) 이다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2206%20%EB%B2%BD%20%EB%B6%80%EC%88%98%EA%B3%A0%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0/main.cpp

devxb/JJUNalgo

코드에 주석을 달아놨다.