[백준] 2206.벽 부수고 이동하기(C++)

2206. 벽부수고 이동하기

시도

사실은 처음에는 모든 벽을 탐색하여 하나씩 0으로 바꾸고 bfs를 수행했을 때의 결과를 구하는 방식으로 구현을 했다.

당연히 이는 시간초과..

질문게시판에 상당히 좋은 필독서가 있었다.

해설

즉, 해당 문제는 단순히 현재 위치를 저장하는 다른 BFS문제의 방식이 아닌, '현재 상태'를 저장하는 방식으로 문제를 해결해야 한다.

• 현재 위치 + 현재 상태인(벽을 부순 적이 있는가)를 visited 배열과 큐에 저장한다.
  • (다음 방문 할 위치의 visited 값) = (현재 위치의 vistied 값) + 1 방식으로 최단 거리를 탐색한다.
    
    
• 벽을 부수기 전과, 부수고 난 후의 최단거리 상태를 섞어 계산할 수는 없기 때문에 2차원 배열의 visited 를 2개(부수기 전, 부순 후)로 둔다.
  • 또는 3차원 배열을 활용(이 방식을 채택하여 구현했다.)
    
    
• 이 문제는 두 가지의 세계선이 존재한다고 생각하면 편하다. (like 이세계물)
  • 벽을 한번도 부순 적이 없는 경우.
  • 벽을 한번이라도 부순 적이 있는 경우.
    
    
• 현재 벽을 부순 적이 없고, 벽을 마주 할 경우,
  1. 해당 벽을 부수고, 벽을 부수고 난 후의 상태를 저장하는 visited 배열로 넘어가 최단거리를 찾는다.

     visited[next_x][next_y][breaked] = vistied[x][y][not_breaked] + 1

  2. 동시에 벽을 부수지 않을 경우의 수는 계속 진행된다.
     그래야 다음 마주하게 될 벽도 감지할 수 있기 때문이다.

     visited[next_x][next_y][not_breaked] = vistied[x][y][not_breaked] + 1

     
     
• 벽을 부순 적이 없는 세계관에서 위 수행이 반복된다.
  
  
• 동시에 벽을 부순적이 한 번이라도 있는 세계관에서도 visited 배열을 바탕으로 최단거리를 찾는다.
  • 즉, 갈 수 있는 곳이라면, 벽을 부순 여부와 상관없이 다음으로 이동한다.

    visited[next_x][next_y][break_state] = vistied[x][y][break_state] + 1

구현