[BOJ] 백준 6087. 레이저 통신

▶문제설명

[BOJ] 백준 6087. 레이저 통신

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

▶Hint

---

BFS & DP 문제이다.

각 좌표에서 꺾인 횟수의 최소값을 저장할 2차원 배열을 만들고,

좌표, 이전 방향, 꺾인 횟수에 대한 정보를 관리할 구조체를 하나 만들어서 BFS를 수행하면 된다.

1. 처음에 상/우/하/좌 네 방향에 대하여, 시작점 좌표와 꺾인 횟수 0으로 큐에 push한다.

2. 시작점 좌표의 꺾인 횟수 최소 값을 0으로 한다.

3. 다음 이동할 방향이 그대로이거나 반대 방향인 경우 꺾인 횟수는 그대로 넘겨주고,

   다음 이동할 방향이 90도로 꺾인 경우 꺾인 횟수를 1 증가시켜 큐에 push하며 BFS를 수행한다.

   큐에 push하는 조건이 중요한데,

   다음에 위치할 좌표에서의 꺾인 횟수가 이전에 저장된 값보다 작거나 같은 경우에만 값을 변경해주고 push한다.

   (해당 좌표에 도착했을 때 진행 방향이 다를 수 있기 때문에 작은 경우만 고려할 경우 답이 나오지 않음)

4. 큐가 비워질 때 까지 수행하고 나면,

   모든 좌표에 대해 꺾인 횟수 최소값이 저장된다.

▶Solution