[BOJ 2178] 미로 탐색 (C++)

Problem

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

2178번: 미로 탐색

Comment

2178번 문제의 입력이 기다란 string type임을 알 수 있습니다. 따라서 입력을 받은 후 배열에 넣어주기 위해 일일이 숫자로 바꿔주어야 합니다.

 

해당 코드는 BFS를 이용해서 풀었습니다. 접근하는 좌표를 방문했다고 체크한 다음, 현재 좌표('current point') 기준 상하좌우를 탐색해 갈 수 있다면 갈 수 있는 곳에 'current point'에 담겨있는 값의 1을 더해줍니다. 그렇게 된다면 최종적으로 마지막 좌표에서 총 거리가 담기게 될 것입니다.

이 때, 무작정 상하좌우('next point')에 'current point'값의 1을 더해주는 것이 아닙니다. 'next point'를 이미 방문했다면 더했을 때 중복되는 결과를 낳을 것입니다. 따라서 'next point'의 방문 여부를 반드시 파악해야 합니다.

Code

Result

Remark

visited 배열과 다음에 탐색할 queue를 만들어주는 것을 잊지 말아야합니다.