백준 2206 - 벽 부수고 이동하기 (미해결, 틀린 원인)

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

2206번: 벽 부수고 이동하기

** 아직 풀이 없습니다 개인 기록용임 **

한 3시간 넘게 도전했는데 답이 안나온다 ㅜ.ㅜ 풀이를 읽고 접근 방법을 바꿔 다시 풀 예정

 

아이디어

 

(1,1)에서 DFS를 돌린다. DFS는 길을 발견할 경우 평소처럼 진행하지만, 벽을 발견할 경우 하나의 행동 패턴이 추가된다. 벽을 부술 수 있는 횟수 break_chance가 1일 경우, 일단 chance를 제거한 뒤 현재 만난 벽을 부수고 그 경로로 DFS를 진행한다. 벽을 부쉈는데 도착지까지 도달하지 못할 경우 벽을 부순 위치까지 방문 기록을 제거하며 복귀하고, break_chance를 1로 되돌린다.

 

DFS 수행 중 거리는 dist 배열에 저장한다. 현재 위치에서의 dist는 경우에 따라 2가지 값을 가질 수 있다.

 

먼저, 다음의 경우 (방금 전 위치의 dist 값 + 1)이 된다.

1) dist값이 0인 경우 : 처음 방문하므로 거리 갱신

2) dist값이 0이 아니지만 chance가 1인 경우 : '벽을 부숴  DFS를 수행했지만 도착지를 찾지 못했다' 라는 의미이므로 현재 dist에 저장된 값은 잘못된 값임. 따라서 갱신

 

다음의 경우에는 min(현재 값, 방금 전 위치 값 + 1)이 된다.

1) chance가 0이고 dist값이 0이 아닌 경우 : 새 경로를 시도하는 중이므로 현재 dist값과 비교해 더 작은 거리를 저장

2) 현재 위치가 도착지인 경우 : 1)과 동일

 

처음 쌩 DFS에서 여러 반례를 테스트하며 보완을 거듭한 결과, 위 내용을 구현한 코드로 질문 게시판에 있는 TC는 다 통과할 수 있었다. 하지만 벽의 개수만큼 DFS를 수행하다보니, O(n^3)의 시간 복잡도가 걸려 n이 1000 정도만 되면 TLE가 뜨게 된다....

 

다른 분들의 풀이를 찾아보니 DFS 대신 BFS를 사용했다. 나는 문제는 들입다 푸는데 각 그래프 탐색 알고리즘의 특성과 차이를 제대로 이해하지 못해서.. 이것도 한번 정리해야겠다.  또 3차원 visited 배열을 통해 벽을 부순 경우와 부수지 않은 경우를 나눠서 탐색을 수행한 듯 하다.