amjong   5년 전

입력을 받은 뒤

시작점의 좌표, 도착점의 좌표를 저장해놓고

(시작점은 두개의 C중 좌상단에 가까운 쪽으로 정함.)

시작점을 시작으로 BFS를 돌려서

다음 칸의 거울의 최소 횟수보다 작은 경우에만 이동하도록 했습니다.

시작점으로부터 각 칸에 도달하기 위해서 놓아야하는 최소 횟수 : int check[101][101] 에 기록하였습니다.

이러면 모든 칸에 대해서 시작점으로부터 그 칸으로 이동할 때 놓아야하는 거울의 최소횟수가 기록되게 되고,

BFS가 모두 끝난 뒤 check 배열에서 도착점의 좌표로 놓아야하는 거울의 최소 횟수를 얻어 출력하였습니다.

부탁드리겠습니다.(__)

djm03178   5년 전

단순히 어떤 칸에 먼저 도달하는지만 필요한 게 아니라, 어느 방향으로 가던 건지도 중요합니다.

아래와 같은 예시에서 아래 방향이 먼저 큐에 들어가기 때문에 1행 0열은 왼쪽 방향으로 가는 것이 먼저 큐에 들어가고, 아래 방향으로 가는 것은 무시됩니다. 하지만 왼쪽 방향으로 가던 것은 실제로는 아래로 다시 한 번 꺾어줘야 하므로 손해가 납니다.

그리고 71번째 줄과 같은 코드를 써야 하는 것은 BFS가 아닙니다. 이 문제에서 카운트해야 하는 단위는 거울의 개수인데, 한 칸 단위로 방문을 하고 있기 때문에 이미 방문한 적이 있어도 다시 방문해야 하는 일이 벌어진 것입니다. 한 번 거울에서 반사가 되었다면, 막히는 곳이 나올 때까지의 모든 좌표를 동시에 큐에 넣어줘야 합니다.

amjong   5년 전

매번 질문 글 올릴때마다 구체적으로 댓글 달아주시는데 정말정말 감사합니다..

올려주신 반례 통해서 71번 줄에 > 였던걸 >=로 바꾸니까 바로 통과됐습니다..

정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.