[programmers] 경주로 건설

---

로직

1. board를 돌면서 direction, cost를 함께 가지고 이동한다.

2. (0, 0)에서 밑으로 가는 것과 오른쪽으로 가는 것 두개를 각각 bfs를 사용해 가격을 확인한다.

3. x = y = len(board) - 1 이 되면 answer에 넣고, answer중에 최소값을 구한다. 

   answer에 들어가는 값은 (0, 0, down)과 (0, 0, right)에서 각자 bfs를 돈 결과이다.

4. near에 (dx, dy, direction)을 넣은 다음에 (x, y)에서 near을 돌면서 xi, yi, new_cost를 구한다.

   다음칸이 0이면서 visit[xi][yi]이 0이거나(아직 지나가지 않음) 기존의 값보다 작은 경우 새 가격으로 갱신해준다.

 

코드

 

주의할 점

1. bfs를 돌때 처음에 q = deque([[0, 0, 'down', 0], [0, 0, 'right', 0]])을 넣으면 down경우와 right경우가 동시다발적으로 진행이 됨

   해결책 : down, right을 따로따로 진행해야한다.