인프런 커뮤니티 질문&답변
작성한 질문수
3-K 시간초과 질문입니다
해결된 질문
작성
·
36
0
영상 보기전에 문제를 먼저 풀어보았는데
로직
arr에 L 하나! 좌표를 p_y, p_x 담기
반복 {
한번 반복될때 마다 ans++
del_y, del_x 두 queue를 만들고
2중 for문 돌면서 빙산깍습니다 만약 빙산"X" 라면
del_y, del_x 에 push 합니다
2중 for문이 끝나면 del_y, del_x에 있는 좌표들을 "." 로 수정합니다
맵 bfs 돌면서 L 2개가 만날수 있는지 체크합니다
방문배열 초기화!
만날수 있다면 ans 변수 출력
}
http://boj.kr/e5a6ee722f5b467ea793402242eb25f0
2% 시간초과가 뜨는데 어떻게 최적화를 해야할까요..
답변 2
0
안녕하세요 ㅎㅎ
이문제는 시간이 정말 타이트한 문제입니다. 즉, 최적화시킬 수 있을만한 것은 무조건 최적화를 시켜야 하는데요. ㅎㅎ
bool find_bfs()
{
int cnt = 0;
queue<int> qy;
queue<int> qx;
qy.push(p_y);
qx.push(p_x);지금 이 코드를 보시면 시작지점부터 다시 시작하는 것을 볼 수 있습니다.
a -> b
a -> b -> c
a -> b -> c -> d
이렇게 중복되어서 탐색하는 경로가 생기게 됩니다. queue 2개를 사용해서 이런 부분이 발생되지 않도록 고쳐주시면 됩니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
ppppabsoo2님께서 작성하신 로직을 보고 몇 가지 조언을 드리겠습니다. 현재 코드에서 시간 초과가 발생하는 주요 원인은 두 가지입니다: 빙하 녹이는 과정에서 불필요한 탐색과 BFS 탐색에서 중복된 계산이 발생하는 경우입니다.
빙하 녹이기 최적화:
- 현재 모든 빙산을 반복문으로 탐색하면서 깎고 있는데, 이는 매우 비효율적입니다. 빙산이 깎일 위치를 추적하여 큐에 저장하고, 매번 해당 큐를 탐색하여 빙하를 녹이는 방식으로 변경해보세요. 이미 녹은 부분 주변의 빙산만 탐색하게 되면 탐색 범위를 줄일 수 있습니다.
- 현재 모든 빙산을 반복문으로 탐색하면서 깎고 있는데, 이는 매우 비효율적입니다. 빙산이 깎일 위치를 추적하여 큐에 저장하고, 매번 해당 큐를 탐색하여 빙하를 녹이는 방식으로 변경해보세요. 이미 녹은 부분 주변의 빙산만 탐색하게 되면 탐색 범위를 줄일 수 있습니다.
BFS 탐색 최적화:
- BFS를 사용하여 두 백조가 만날 수 있는지를 체크할 때, 매번 방문 배열을 초기화하는 방식은 비효율적일 수 있습니다. 방문 배열과 BFS 큐를 사용하여 이웃한 ‘물’ 부분만 탐색하게 하고, 탐색이 끝난 후 상태를 유지할 수 있도록 해보세요. 이렇게 하면 매턴마다 필요한 최소한의 탐색을 수행할 수 있게 됩니다.
- BFS를 사용하여 두 백조가 만날 수 있는지를 체크할 때, 매번 방문 배열을 초기화하는 방식은 비효율적일 수 있습니다. 방문 배열과 BFS 큐를 사용하여 이웃한 ‘물’ 부분만 탐색하게 하고, 탐색이 끝난 후 상태를 유지할 수 있도록 해보세요. 이렇게 하면 매턴마다 필요한 최소한의 탐색을 수행할 수 있게 됩니다.
이러한 방법을 통해 불필요한 탐색을 줄이고, 프로그램의 성능을 향상시킬 수 있습니다. 관련된 추가 정보는 아래 게시글에서도 참고해 보실 수 있습니다:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.