경로찾기 (1) 썸네일형 리스트형 [백준 경로찾기] DFS 문제, 2차원 벡터 활용 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 경로찾기 문제로 문제를 푸는 알고리즘은 다음과 같다. 1) q.pop() 나온 노드를 현재노드로 지정 2) 현재노드에서 주변노드에 방문 안했으면 방문처리후, q.push() 이 문제는 매우 간단하나 시간초과를 막기위해 문제를 풀기위한 시스템을 마련하는 방법이 중요하다. 현재노드에서 주변노드를 탐색할 때, for문으로 주변 노드를 모두 다 확인하면서 연결되있는 여부를 검사한다면 노드가 100개존재할 때, 요구되는 시간이 매우 많아질것이다. .. 이전 1 다음