D36CHOI

www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 곧 있을 LG 코딩테스트에 앞서 기본기 복습 겸, 가장 기본적인 DFS / BFS 문제를 풀어보았다. 특징은 DFS 는 재귀함수가 아니라 stack 을 활용해 만들었다는 것. (기본적으로 같은 반복횟수면 시스템상 재귀방식보다 stack 이 속도가 빠르다고 한다) 그리고 기존엔 visited 배열을 True Or False 로 했다면 여기선 visited 에 방문한 노드의 번..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 분류: BFS N 의 위치에서 K 까지 가는 최소의 이동 횟수를 구하는 문제. -1 , +1 , *2 의 3가지 경우가 가능하다. depth가 N일 때 전체 경우를 확인하는데에 O(N^3) 의 시간이 소요된다! 그래서 visited 배열을 통해 방문한 노드에 대해선 해당 노드 이후의 진행은 거부한다. 그 이유는 BFS 기 때문에, 이미 방문한 위치에 대해 다시 방문을 한..