[백준 경로찾기] DFS 문제, 2차원 벡터 활용

https://www.acmicpc.net/problem/11403

11403번: 경로 찾기

경로찾기 문제로 문제를 푸는 알고리즘은 다음과 같다.

1) q.pop() 나온 노드를 현재노드로 지정

2) 현재노드에서 주변노드에 방문 안했으면 방문처리후, q.push()

 

이 문제는 매우 간단하나 시간초과를 막기위해 문제를 풀기위한 시스템을 마련하는 방법이 중요하다.

 

현재노드에서 주변노드를 탐색할 때, for문으로 주변 노드를 모두 다 확인하면서 연결되있는 여부를 검사한다면 노드가 100개존재할 때, 요구되는 시간이 매우 많아질것이다. 따라서 시간을 줄이기 위해 연결되어있는 노드만 바로바로 찾아서, 방문했는지 여부만 검사하는 것이 중요하다.

 

따라서 맵은 2차원벡터를 통해 연결되어있는 노드만 벡터.push_back()하였고 초기에 벡터는 행을 생성하지 않고 열만 생성하여 필요한 만큼만 행을 추가하는 것이 중요하므로 https://powerofsummary.tistory.com/21?category=833046에서 2번의 경우이다.