https://www.acmicpc.net/source...
코드가 많이 달라지긴 했는데 해결했습니다~
하지만 아직도 위에 코드가 시간 초과가 나는 이유는
잘 모르겠습니다...
11048번 - 이동하기
간단하게
2 2
0 1
0 0
이라는 입력이 들어온다고 생각해봅시다.
작성자 분의 코드에 로는 처음에 dp는 전체가 -1로 초기화 되어 있을거고, X+1 로 탐색을 진행하게 되는 코드입니다.
이 때, [1][0]을 갔을때, [1][1]의 값은 -1이고, 이 값은 current.V에 해당하는 0보다 작으므로, 큐에 [1][1]이 추가 됩니다.
이후에 [0][1]을 탐색하는데, [1][1]의 값은 0이고, 이 값은 cuurent.V에 해당하는 1보다 작으므로, 큐에 [1][1]이 한번 더 추가됩니다.
이런 불필요한 연산이 1000 * 1000 크기에 쌓이게 되면 시간초과가 나게 됩니다.
이는 탐색의 조건 판단에 대한 문제로, DFS는 현재 노드에 대해서 검사해도 되지만, BFS는 큐에 넣을때 검사를 진행해야합니다.
친절한 답변 감사드립니다~
댓글을 작성하려면 로그인해야 합니다.
dksh_2023010518 1년 전
왜 시간초과가 뜨는지 모르겠습니다