7569번 - 토마토
3차원 리스트 bfs로 구현했고 방문처리도 in으로 하면 시간복잡도가 더 높다고 들었어서 True/False로 처리했는데
파이썬이나 pypy나 둘다 1%에서 시간초과가 나옵니다 ㅠㅠㅠ 어디가 느린지 잘 모르겠어서 질문 여쭤봅니다 ㅠㅠ
아직 많이 부족하지만 꾸역꾸역 문제를 풀고 올라온지라 시간복잡도 개념을 정확하게 이해를 못해서 어디를 개선해야할지 감도 안옵니다.. 도와주세요 ㅠㅠ
line 41 ~ 45에서
이미 다른 탐색에서 탐색한 토마토도 탐색을 시도하여 O((NMH)^2)이 됩니다.
감사합니다..! 3중for 안에서 중복으로 확인안하고 한번에 연결된 토마토를 탐색하고 따로 방문처리 해주는것으로 시간을 줄여봤더니 해결됐습니다..!
python3으로는 시간초과나서 pypy로 제출했더니 맞았습니다..!
댓글을 작성하려면 로그인해야 합니다.
danny9883 8달 전
3차원 리스트 bfs로 구현했고 방문처리도 in으로 하면 시간복잡도가 더 높다고 들었어서 True/False로 처리했는데
파이썬이나 pypy나 둘다 1%에서 시간초과가 나옵니다 ㅠㅠㅠ 어디가 느린지 잘 모르겠어서 질문 여쭤봅니다 ㅠㅠ
아직 많이 부족하지만 꾸역꾸역 문제를 풀고 올라온지라 시간복잡도 개념을 정확하게 이해를 못해서 어디를 개선해야할지 감도 안옵니다.. 도와주세요 ㅠㅠ