zero2hero2   3년 전

본 문제는 하나의 토마토를 bfs로 끝까지 탐색하지 않고 토마토 하나마다 한 번만 6방향을 탐색하는 것의 반복입니다.그런데 이 글을 보시는 여러분은 여기까지 실행하셨는데도 시간초과가 나서 답답한 분들이실 것입니다. 그렇다면 탐색하는 조건을 충족하는 토마토를 찾을 때 비효율적인 방법으로 탐색하고 있지는 않은지 한 번 확인해 보세요. 본 문제는 가로,세로,높이가 각각 100까지 가능해 100000까지 탐색해야하는 문제입니다.따라서 필요한 좌표만 골라내 탐색하는 것이 필요합니다. 

그 방법은 바로 deque를 6방향 탐색할 때 bfs에서만 사용하는 것이 아니라 필요한 좌표를 집어넣는데에도 사용하는 것입니다. 즉 deque를 두 번 사용하는 것입니다. 처음에 입력받을 때 별도의 deque인 next를 만들어 값이 1인 좌표를 next에 넣은 뒤 꺼내어  bfs함수의 입력값으로  사용합니다. 또한 bfs의 결과로 나온 조건에 맞는 좌표를 next에 집어넣습니다. 그렇게 되면 다음에 탐색할 좌표가 없을 때까지 실행되기 때문에 더 이상 익을 수 없을 때까지 전부 실행됩니다.

설명만으로 어려우실 것 같아 아래에 제가 짠 코드를 첨부했습니다. 13-21,40,45-47 라인에 주의해서 봐주시면 될 것 같습니다

저도 이 문제를 풀면서 왜 시간초과가 나나 답답했고 오래 생각하여 겨우 이 아이디어를 떠올릴 수 있었습니다. 이 문제를 푸는 다른 분들은 시간초과의 원인을 알고 시간을 아끼실 수 있도록 글 남겨봅니다

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