[백준 5213] 과외맨

[ 백준 5213 : 과외맨 ]

BFS + DFS 를 이용하는 문제

일단 맵이 정말 특이하게 생겼다. 보통 보던 N*M의 직사각형의 모양이 아니라 짝수번째 행은 맨 처음과 마지막 열이 비어있다.

문제를 풀 때 고려할 것은 이것 뿐인것같다.

처음 0,0에서 출발해서 상하좌우를 체크하며 돌아다니는 것은 BFS를 이용했고,
문제의 답을 출력해야하는 경로와 지나온 칸의 수는 DFS를 이용했다.

일단 문제에서 그려진대로 똑같이 맵을 만들었다. 삼차원배열로 맵을 입력받았는데
MAT이라는 변수의 [0][X좌표][Y좌표] 는 입력하는 값들, 그리고 [1][X][Y]에는 해당 맵의 숫자를 입력했다.
내가 만든 맵은 0행0열부터 시작하므로 짝수행은 0~2*N-1까지 열이 존재하고 홀수행은 1~2*N-2까지 열이 존재한다.
홀수행과 짝수행은 ( 행&1 )으로 쉽게 구할 수 있다.

그리고 마지막 경로를 DFS로 탐색하기 위해 해당 번호마다 지나온 번호를 입력했고,
한번 탐색했던곳을 쓸모없이 다시 탐색하지 않기 위해서 지나온 좌표마다 그때까지 이동한 순서를 넣어줬다.
이 처리를 함으로써 한 번 지나왔지만 만약 그곳을 3번만에 왔고, 지금은 2번만에 그곳을 가는 것이라면 해당 좌표를 큐에 넣는 식으로 구현했다.
또 하나의 처리를 더해줬는데,
맵의 한 번호마다 두개의 좌표가 달려있어 이를 묶어서 처리하기 위해 (VI[500*500]) 변수를 설정해 몇번만에 그 번호로 왔는지를 저장했다.

따라서
이차원 배열로 해당 좌표까지 얼마만에 왔는지, 일차원 배열로 해당 번호까지 얼마만에 왔는지, 일차원 배열로 지나온 좌표를 저장.
이런식으로 구현했다.