Baekjoon 1600 말이 되고픈 원숭이 JAVA

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

1600번: 말이 되고픈 원숭이

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201600

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map이 주어지면 왼쪽 위에서 오른쪽 아래까지 가는 최솟값을 구하는 문제다.

조건은 원숭이는 기본적으로 상하좌우로 한 칸 이동 가능하며

말을 따라 하기 위해 체스 말처럼 이동이 가능하지만 k 번만 가능하다.

​

해당 문제는 BFS를 이용해서 해결했고, 방문 배열을 3차원 배열로 활용하였다.

k 값에 따라서 같은 위치라도 달라지기 때문.

​

큐도 데이터가 4개 들어가도록 하였는데 y좌표, x좌표, k 값, 이동 횟수를 저장한ㄷ다.

​

1. 처음 시작 좌표인 0,0과 k, 0(이동 횟수)를 큐에 삽입하고 BFS를 한다.

2. 큐가 빌 때까지 반복하며 먼저 큐의 데이터를 가져온 뒤 만약 가져온 데이터 좌표가 오른쪽 아래면 해당 이동 횟수를 출력하고 끝낸다.

3. 2번이 아니라면 처음 하우 상좌를 방문하면서 방문 가능하면 방문 배열 방문 및 큐의 데이터를 삽입한다.

4. 만약 큐에서 뺸 k 값이 0이면 다음 반복으로 간다.

5. 4. 가 아니라면 말 이동에 대한 방문을 진행하면서 방문 배열 및 큐의 데이터를 삽입한다.(k 값-1 해주면서)

6. 다시 2번으로 돌아가 반복하며 만약 이동 횟수를 출력하고 끝내지 못한 채로 큐가 비었다면 -1을 출력해 준다.