2206_벽 부수고 이동하기 ( BFS )

본 포스팅은 문제에 대한 접근에 문제가 없지만 코드를 구현함에 있어서 어려운 분들에게 도움이 되었으면 하고자하여 작성하게 되었습니다.

 

2206 벽부수고 이동하기

 - 이 문제는 단순한 미로찾기에서 벽을 부술 수 있는 기회가 1회 추가된 복합 문제이다

 - 단순히 접근하면 지도 전체에서 벽을 1번 부순 모든 경우의 수를 brute force 형태로  찾은 뒤 BFS로 각 경우마다 최단 거리를 구하여 결과를 도출할 수 있다

 - 하지만 그럴 경우 당연히 시간초과의 늪에 빠지게 된다.

 - 이에 대해 고민을 한 결과 벽을 부술 수 있는 상태 값을 만들어 문제를 해결하였지만 " 틀 렸 습 니 다 " 만 나왔을 뿐이다...ㅂㄷㅂㄷ

 - 여러 반례를 확인해본 결과 벽을 부수고 목적지까지 가다가 새로운 벽을 만났을때, 벽을 부수지 않고 목적지까지 가다가 새로운 벽을 만났을때에 대한 문제가 있었다. 반례는 아래 추가 내용을 참고하자

 - 문제 풀이는 BFS을 이용하여 해결하였다.

 - 자세한 내용은 코드의 주석을 참고하자

 

* 해당 문제는 글쓴이가 많이 헤맸던 문제기에 반례에 대한 추가 내용을 아래와 같이 첨부

 

반례

 - 벽을 먼저 부수고 목적지까지 가다가 새로운 벽을 만나 더이상 가지 못할때

 - 벽을 부수지 않았을 때와 벽을 부쉈을때 같은 경로를 지나간다는 가정 하에

 - 방문 확인 배열을 하나만 사용한다면, 한 경우에 의해 다른 경우가 진입을 못할 수가 있다.

 - 따라서 벽을 부수고 탐색 위치에 도달했는가? 와 벽을 부수지 않고 탐색 위치에 도달했는가?에 대한 두 상태에 대한 방문 확인 배열을 구성해주어야한다.

 - 자세한 내용은 코드의 주석을 참고하자