숨바꼭질1 [백준] 1694 숨바꼭질 BFS를 잘 활용하면 되는 문제. 그래프를 잘 생각 해보자. 각 숫자들을 그래프의 노드라고 했을 때, 1만큼 떨어진 이웃하는 숫자는 양방향 간선으로 다 이어져 있고, x노드에서 2x노드로 가는 간선들이 있다. BFS는 모든 정점과 간선을 살펴보는 알고리즘이므로 시간복잡도는 O(|V| + |E|)인데, V = 100,000, E < 300,000 이면 충분할 거라고 생각했다. 참고로 memset에 사이즈를 sizeof(d)/sizeof(int) 라고 했다가.... 수없이 실패를 했던 문제이다. 나머지는 최단거리를 구하는 BFS문제로 직관적으로 쉽게 풀 수 있다. #include #include #include using namespace std; int d[100001]; int main() { int n.. 2019. 9. 12. 728x90 이전 1 다음
