[2020 카카오 인턴십] 경주로 건설

 

문제: https://programmers.co.kr/learn/courses/30/lessons/67259

---

https://codingjuny.tistory.com/41

 

위 출처를 참고하여 "비용"으로 BFS를 돌려야한다는 아이디어를 얻었습니다.

 

 

경주로를 설치하면서 식별할 수 있는 정보는 3가지입니다.

그래서 저는 상태공간을 VISITED[DIR][N][N] 으로 선언하였습니다.

VISITED[DIR][N][N] 정의: DIR 방향으로 N,N좌표에 도로를 놓는 최소 비용

 

방향, Y좌표, X좌표 (방향 정보가 있기 때문에 Y,X, 좌표 하나만 가지고 움직여도 경주로를 표현할 수 있습니다.)

 

도로를 설치하면서 모든 방향을 탐색해봐야 합니다.

(단, 현재 진행하던 방향과 반대방향은 무한 루프에 빠지게 되니 그 방향은 제외하고 3방향 탐색만 합니다.)

 

그렇게 BFS 탐색을 하면서 다익스트라처럼 

'현재 상태공간을 더 저렴한 비용으로 방문할 수 있다면' QUEUE에 다시 넣어줍니다.

 

BFS 탈출조건은 도착좌표가 board[N-1][N-1] 이면 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/KAKAO2020_04.java