mantissa   2년 전

어떤 분이 올려주셨던 예전 대회 케이스들은 전부 확인했습니다. 막막해서 질문 올립니다.

불 먼저 상하좌우로 뻗어나가며 도달하는 시간을 계산하여 ftime[x][y]에 저장합니다. 이 때, 따로 갱신하는 부분은 두지 않았습니다. 어떤 좌표에 처음 도달한 불이 가장 빨리 도착한 불이라고 가정했습니다. ftime[x][y]는 처음으로 -1로 세팅해두고 첫 입력으로 들어온 불은 0, 이후는 뻗어나갈 때마다 +1 해주고 있습니다.

이후, jBFS()에서 사람에 대한 BFS를 진행합니다. 다음으로 이동할 위치가 배열의 범위를 벗어난다면 가장 자리에 도달했다고 판단하고 ans값을 갱신하고 있습니다. 이 ans값은 임의로 1e9로 설정했고 queue에 들어있던 해당 위치에 도달한 시간+1과 비교합니다. 이후에 BFS가 끝나고도 ans값이 1e9인 경우 IMPOSSIBLE로 판단합니다. ftime[x][y]의 경우, 불이 도달하지 않았던 위치는 -1로 그대로 남겨져 있습니다. 이에, jBFS()에선 이동할 위치의 ftime값이 -1인 경우 불이 도달하지 않은 안전한 위치라고 판단, 방문합니다. -1이 아닌 다른 값일 경우 ftime값보다 이동할 시간이 더 짧을 경우 먼저 도착한 것으로 판단, 방문합니다. 이 때도 마찬가지로, 한 번 방문했던 지점은 visited 배열을 통해 다시 방문하지 않습니다.

긴 글 읽어주셔서 감사합니다.

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