[c++] 백준 벽 부수고 이동하기(2206), BFS

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

• NxM 형태의 맵에서, 0은 이동가능, 1은 벽으로 이동 불가. 상하좌우로만 이동가능.
• 좌측 상단(1,1)에서 우측하단(N,M)까지 이동 가능한 최단 거리 출력. 이동 불가시 -1 출력.
• 벽을 1 개만 부실 수 있음.

 

풀이

• 일반적으로 최단거리 출력은 방문여부 체크가 중요함. (map과 방문여부 체크하는 map_check를 따로 만듬)
  이미 방문한 곳은 최단거리가 아니라고 가정하기 때문. 
• 하지만, 이 문제는 벽을 1개 부실 수 있기 때문에 이미 방문한 곳이라도 벽을 부수고 방문했느냐 혹은 부수지 않고 방문 했느냐로 나뉘게 됩니다.
• 다시 말해, 방문여부 체크를 벽을 1개 부셨을 때와 부수지 않았을 때를 나누어서 생각해야 합니다.
• 따라서, map_check를 3차원으로 구성하여 벽을 부술때의 map과 그러지 않았을 때의 map을 분리하여 방문여부를 체크 및 최단거리를 계산해주어야 합니다.
• 벽을 부수고 난 후에 경로가 이전에 방문한 적이 있다면 그것은 최단거리가 될 수 없습니다. 
• 하지만, 벽을 부수지 않았는데, 벽을 부순 경로가 이미 방문한적이 있다면, 그곳은 방문 가능해야 합니다. 
  다시 말해, 벽을 부순 경로와 부수지 않은 경로를 분리하되, 부수지 않은 경로는 부순 경로의 방문여부에서 자유로워야 합니다. 반대로 벽을 부순 경로는 부수지 않은 경로보다는 짧아야 하므로 간섭을 받아야 합니다. 

 

코드

• 입력을 각 줄마다 String으로 받습니다.
• 3차원 벡터를 생성해줍니다. 벽을 부술 때와 아닐 때를 구분하기 위함입니다. 
  3차원 벡터의 사용법은 아래 링크를 참고해주세요.
  https://forward-gradually.tistory.com/55
  이 문제는 벽을 1개만 부술 수 있기에 3차원의 높이를 2로 설정하였지만, 만약 벽을 10개 부순다면 10개로 생성해야 할 것 같습니다.
• BFS 알고리즘을 통해 벽을 1개 부술 수 있으면서, 최단거리를 찾습니다.

[c++] 3차원 배열(백터) 선언 및 초기화

 

• BFS 함수입니다
• map에 대한 정보와 map의 방문 여부를 체크하는 map_check를 참조자(&)를 통해 받아옵니다. 이를 통해 벡터를 복사하는 것이 아닌 주소로 접근 가능하도록 해줌으로 시간을 단축시킬 수 있습니다.
• tuple을 이용하여 맵에 한 좌표(x,y)와 broken 했는지 여부를 나타내는 것을 하나의 쌍으로 큐를 생성합니다.
  tuple 사용법은 아래 링크를 참고해주세요.
  https://forward-gradually.tistory.com/56

[c++] Tuple 사용법

 

• 무한반복문을 통해 큐가 비어질때까지(즉, 이동할 수 있는 것이 없을 때까지) 반복합니다.
• tie()를 이용하여 tuple의 값들을 각각의 변수에 저장합니다.
• 상하좌우 좌표를 이동하면서 이동 가능한 좌표들을 큐에 쌓고, map_check에 이동여부 체크 및 현재까지 이동한 거리를 갱신하여 저장해줍니다. 
• 여기서 중요한 것은 현재 큐의 좌표의 값이 이전에 벽을 부신적이 있는지에 대한 여부를 생각해주어야 합니다. 
  벽을 부셨다면 broken=1이 될 것이고, 다음 벽을 만났을 때에는 부수면 안됩니다.
  벽을 부수지 않았다면 broken=0이 될 것이고, 다음 벽을 만낫을 때 부술 수 있습니다. 그러면 broken=1로 갱신되서 다음 좌표의 값이 큐에 다시 쌓이겠죠.
• 결국, BFS를 통해서 모든 가능한 경로를 탐색하는데 다음과 같은 사항을 고려한다고 볼 수 있습니다.
  1) 이전에 방문했는지 여부
  2) 벽을 부순적이 있는지 여부
  3) 벽을 부수었던 경로가 벽을 부수지 않았던 경로를 간섭해서는 안됩니다. 다시말해, 이 둘을 분리해서 방문여부를 체크해야 합니다. 이를 위해, 3차원 벡터로 공간을 확장하여 벽을 부수면 높이가 다른 공간에서 거리를 계산해야 합니다.
  
  

알게 된 점

• 최단거리를 BFS로 구하는 문제는 방문여부 및 현재까지 이동한 거리를 맵의 좌표마하 할당해가며 최종 목표지점에 가장 먼저 도달했을 때의 거리가 곧 최단거리가 됩니다. 
• 하지만 이동할 수 없었던 곳을 방문 가능하다는 변수가 생길 때에는 단순히 방문여부만을 체크하여 이동하지 않은 경로만 가게 된다면 최단거리를 찾을 수 없는 경우가 생깁니다.
• 이를 위해, 이전의 룰을 깨트리는 경우에 대해서 따로 방문여부를 체크해야 하고, 그 과정에서 벽을 부순 것과 부수지 않은 것에 대해 최단거리의 우선순위가 무엇일지를 고민할 수 있었던 문제였습니다.
• 3차원 이상의 처리도 유연하게 생각할 수 있게 되었습니다.

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%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(2206)%20%EC%9E%AC%EC%8B%9C%EB%8F%84.cpp