[c++] 백준 벽 부수고 이동하기 3(16933), bfs, 반례모음

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

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.

이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

반례모음

1 1 1 0 1

3 3 2 011 111 110 -1

2 4 2 0111 0110 7

3 3 10 011 011 000 5

3 3 3 011 111 110 7

5 5 4 01101 11100 00111 11110 00110 10

 

풀이

백준 벽 부수고 이동하기 2(14442) 문제의 풀이를 먼저 참고하시면 좋습니다.

https://forward-gradually.tistory.com/74

[c++] 백준 벽 부수고 이동하기 2(14442), bfs

• 여기에는 문제의 여러 조건을 생각해야 합니다.
  1. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다.
  2.  낮과 밤이 번갈아가면서 등장
  3. 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
  4. 벽은 낮에만 부술 수 있다.
• 즉, 일반적인 BFS로 탐색하되 벽을 만났을 때, 현재 상태가 낮 or 밤 인지와 벽을 부술 수 있는지를 고려해야 합니다.
• 다시말해, 다음과 같은 조건문이 필요합니다.
  1. 다음 탐색 좌표가 벽일 경우
    1) 현재 상태가 낮인 경우 
       - 벽을 뛰어 넘을 수 있습니다.
    2) 현재 상태가 밤인 경우
       - 벽을 뛰어넘지 못하고, 제자리에 있습니다.
  2. 다음 좌표가 벽이 아닐 경우
    - 일반적인 bfs를 수행하면 됩니다.
• 위의 조건문은 대략적인 부분이고 다음과 같이 세부적인 사항들을 녹여내야 합니다.
  1. 낮과 밤의 상태에 대한 값들을 계속 저장
  2. 현재까지 벽을 부순 것을 카운트 -> 3차원 배열에서 층으로 대체합니다.
  3. 밤에 제자리에 있을 경우를 고려합니다.
     - 제자리에 있어도 한 번 이동한 것으로 카운트 되기 때문에, 다른 변수에 제자리에 있을 때 +1을 해줘서 추후에 낮에 해당 값을 합산하여 계산할 수 있도록 합니다. (보통 이것 때문에 출력값이 +1이 더해서 나오는 오류가 발생)
• 따라서, 저는 아래 코드와 같이 튜플 형태로 변수들을 한번에 모아서 큐에 쌓아 bfs로 처리하였습니다. 
  자세한 사항은 다음 코드챕터에서 다루겠습니다.
• 그 전에 튜플에 대해서 모르시는 분들은 보고 오시면 좋습니다.
  https://forward-gradually.tistory.com/56
  

[c++] Tuple 사용법

 

코드

• 튜플에 들어가는 인자중 "stay"는 밤에 벽을 만났을 때, 제자리에 멈춘 경우에 카운트해줍니다. 추후에 낮에 stay를 더해주어 밤에 제자리에 멈춰 있던 수를 +1해줍니다. 
  ***주의 : 만약 stay를 사용하지 않고 현재 좌표의 map_check에 ++를 해준다면, 벽 이외에 양,옆으로 이동시에 ++해준 값이 더해져 재대로 된 최단거리를 구할 수 없게 됩니다. 
• 낮과 밤은 각각 +1, -1로 설정하였으며, 이를 통제하기 위해 다음 좌표 이동시에 sun_or_mood * -1을 해주었습니다. 

 

알게 된 점

• 여러가지 조건처리에 대해서 보다 잘 다룰 수 있게 되었습니다.
• 큐에 쌓을 때 우선순위를 더욱 분명히 선별할 수 있게 되었습니다.
• 코드 짜는 속도가 상승하였습니다. 

 

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%203(16933).cpp