미로 탈출 문제

N * M 크기의 직사각형 형태의 미로에 갇혀 있다.

동빈이의 위치는 (1,1)이고  미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다

 

---

5 5
11000
01100              10
00110
00011
11111

 

입력 예시      출력 예시

먼저 조건에 해당하는 내용에 대한 입력을 받아야 한다.

따라서, map 메서드를 이용하여 int 형으로 입력받는다

 

그 후, array에 append 메서드를 통하여 list형태로 m개만큼 i번 입력받는다

 

그리고 방향의 경우, 중요한 포인트인데,

우리는 탈출구가 정해져있고, 남,동쪽으로 가는 경우에만 최소의 조건으로 갈 수 있다. 

서쪽이나 북쪽으로 갈 경우 최소의 조건에 해당되지 않기 때문에 남,동의 경우만 방향 설정해준다.

이후에는 이와 같이 bfs 함수를 구현해주면 되는데 result값은 우리가 출력할 값의 변수이며, 이는 현재 지점은 무조건 1로 명시되어 있으므로 초기값도 1로 설정해준다.

 

그리고, 기존의 bfs 알고리즘과 동일하게 queue를 통하여 삽입, 삭제를 통하여 구현해주면 된다.

 

이 때 한 가지 더 유의할 사항은 check라고 명시되어 있는 변수인데, 이는 만약 남,동 두 경우가 모두 1로 채워져있어 두 경우 모두를 더했을 경우 최소의 조건을 만족하지 않는다. 따라서 그 중 한 경우만을 count해주기 위하여 결과값에 -1해주었다.

 

 

이후 결과값을 출력해보면 원하는 값을 얻을 수 있다.