핵심포인트
1.최단거리탐색에서 반환할 answer 공유변수보다 비용을 더 사용중인 큐는 continue시키기.
2.큐를 이용한 최단거리탐색에서 목적지에 도달했다면 바로 answer 공유변수 업데이트하기.
3.큐를 이용한 탐색을 진행하는상황에서
방문한 노드를 체크 후 바로 방문처리하기.
if visited[j] == 0:
visited[j] = 1바로 방문처리안하면 다른 큐에서 중복으로 접근하게 된다.
4.최단거리면 큐를 사용하고 단순 탐색이면 스택만으로도 해결된다.
5.중복방문이 필요한 경우에는 기존 방문 비용과 비교해서 더 나은 경우에만 재방문 하기.
if ( v[next] != -1 ) and ( v[next] <= cnt + 1) :
continue
v[next] = cnt + 1
q.append([next, cnt + 1])파이선은 가능한 리스트를 이용한다. SET이나 딕셔너리는 메모리가 터질 수 있다. 해시테이블 특성상 키 중복을 피하기 위해 다루는 데이터가 많을수록 메모리를 많이 먹는다.
특정 언어로 해결이 안되는 문제도 있다.
https://www.acmicpc.net/problem/1325
BackEnd Developer