백준 6087. 레이저 통신

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

6087번: 레이저 통신

 

최소 갯수의 거울을 놔서 레이저 방향을 바꿔 도착지점에 도달하게 해야한다. 

그런데 어처피 거울은 두가지 종류가 있고 회전이 가능하기 때문에 결국 이 문제는 그냥 시작지점부터 도착지점까지 꺾이는 방향이 몇개인지 구하는 문제였다.

 

최소한으로 방향을 꺾으며 도착지점에 도달해야 한다.

mark[R][C] = val , val은 (r,c)에 도달하는데 사용한 거울의 최소 갯수.

bfs를 사용해서 이동하는데 큐에 이동방향을 저장해주면 이전 위치에서 현재 위치에 오는데 어떤 방향으로부터 왔는지 알수 있다.

이번에 이동하는 위치가 이전에 온 방향과 같다면 거울의 갯수는 그대로일것이고, 

다르다면 거울의 갯수를 1 증가시키면 된다.

이전 위치로는 다시 돌아가지 않도록 해야한다.