16236번 - 아기 상어
안녕하세요, 삼성 SW역량 기출문제 풀다가 시간초과로 문제해결을 못해서 질문드립니다.
질문게시판에 나와있는 반례들은 모두 다 테스트 해봤는데요, 반례들은 다 정답으로 뜨지만 제 소스로 채점하니 2%에서 시간초과가 납니다..
제가 접근한 방식은
1. 맵 전체를 BFS로 순회하면서 상어가 먹을 수 있는 물고기의 위치를 우선순위 큐에 저장 (Priority는 거리, 행, 열 순입니다.)
2. BFS가 끝난 후, 우선순위 큐에서 물고기 위치를 얻음 (우선순위 큐가 비어있다면 먹을 수 있는 물고기가 없다는 뜻이므로 종료합니다.)
3. 물고기를 잡아먹고, 상어크기의 갯수만큼 물고기를 먹으면 상어의 크기를 1 증가
4. 1~3 반복
위와 같이 코딩을 했고, 테스트 케이스 및 질문 게시판에 있는 반례들을 다 테스트해봤는데 잘 됐습니다.
그런데 막상 제출을 하니 2%에서 시간초과가 나네요.
어떤 부분에서 잘못됐는지 알 수 있을까요?
감사합니다.
if (next_r, next_c) not in visited and board[next_r][next_c] <= shark_size:
이부분이 오래걸리는거 아닌가요 ???
@redbin0471
문제 해결한 링크 첨부하겠습니다.
https://empty-cloud.tistory.com/25
댓글을 작성하려면 로그인해야 합니다.
tjdgns9246 4년 전
안녕하세요, 삼성 SW역량 기출문제 풀다가 시간초과로 문제해결을 못해서 질문드립니다.
질문게시판에 나와있는 반례들은 모두 다 테스트 해봤는데요, 반례들은 다 정답으로 뜨지만 제 소스로 채점하니 2%에서 시간초과가 납니다..
제가 접근한 방식은
1. 맵 전체를 BFS로 순회하면서 상어가 먹을 수 있는 물고기의 위치를 우선순위 큐에 저장 (Priority는 거리, 행, 열 순입니다.)
2. BFS가 끝난 후, 우선순위 큐에서 물고기 위치를 얻음 (우선순위 큐가 비어있다면 먹을 수 있는 물고기가 없다는 뜻이므로 종료합니다.)
3. 물고기를 잡아먹고, 상어크기의 갯수만큼 물고기를 먹으면 상어의 크기를 1 증가
4. 1~3 반복
위와 같이 코딩을 했고, 테스트 케이스 및 질문 게시판에 있는 반례들을 다 테스트해봤는데 잘 됐습니다.
그런데 막상 제출을 하니 2%에서 시간초과가 나네요.
어떤 부분에서 잘못됐는지 알 수 있을까요?
감사합니다.