이모저모

해결방법1) SPFA 알고리즘을 활용ㄱ) height 기준으로 정렬ㄴ) 순회하며 SPFA로 돌린다.travel[N][K] : n번째 노드가 k번 이동하였을 때 최소 높이SPFA를 사용한 이유는 다이젝스트라처럼 돌리면 최솟값이 나오지 않는다.(optimal 하지 않다.)단순 bfs를 이용하면 지수복잡도를 가지게 된다.ㄴ-1) 작은 값을 기준으로 순회하기 때문에 해당 노드를 방문하면 이 후 최소값을 가질 일은 없다. 시간복잡도 O(N^2K) 의 복잡도를 가진다. 최대 travel 배열만큼 O(NK)가 큐에 들어갈 수잇고 각각 최대 O(N)만큼 체크하기 때문이다. 2) dp로 풀기점화식은 아래와 같다.dp[n][k] : n번째 노드에서 k번 이동하였을 때 최소 높이dp[n][k] = for n' in edge..

해결방법 bfs를 2번 이용하여 1에서 갈 수 있는 지점(outgoing으로) 및 n에서 갈 수 있는 지점(incoming으로)을 체크한다.즉 1에서 나가는 방향으로 bfs, n에서 들어가는 방향으로 bfs를 돌리면 각각이 모두 가능하면 문제를 해결할 수 있다.시간복잡도 O(V+E)공간복잡도 O(V+E) 아래는 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#de..

해결방법BFS를 이용하여 depth, prev path를 구하면 된다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;typedef pair pii; int n,k,visit[..

해결방법BFS를 활용하여 쭉 순회하면서 이미 방문한 숫자도 depth가 같은 경우 경우의 수를 추가하면 된다.굳이 depth를 저장할 필요없이 훨씬 간단하게 구현할 수 있는데 안했다.....초심 잃은 것인가.....아 그리고 굳이 범위인 100000 보다 크게 잡을 필요는 없다. 왜냐하면 v*2를 해서 10만 보다 큰 값에서 감소하는 것보다 (v-1) * 2와 같이 감소하고 곱하는 것이 depth가 반가량 감소하게 되기 때문이다.나중에 좀 간소하게 짜도록 노력하자.....시간 복잡도는 O(N) 왜냐하면 중복 숫자는 큐에 집어 넣지 않기 때문에~~공간 복잡도는 O(N) 방문과 숫자를 카운트하기 위해서~~~ #include #include #include #include #include #include #i..