그래프2 BOJ 1520 - 내리막길 https://www.acmicpc.net/problem/1520 접근그래프 탐색에서 내리막길로만 건너가는 문제이다. 이 문제의 핵심은 어떻게 모든 경로의 수를 구하냐가 관건이다.기존 BFS, DFS를 사용 시, 모든 경로를 탐색해야 하므로 500x500인 이번 문제에서 시간초과가 발생한다. 이 문제의 핵심은 Y->X와 Z->X로 갈 때, X의 경로의 수는 Y+Z 임을 이용하면 된다.이를 메모이제이션을 통해 DP[movedX][movedY]가 0인 경우(탐색되지 않은 경우)에는 계속 앞으로 전진하고,DP[movedX][movedY]가 0이 아닌 경우(이미 탐색된 경우)에는 DP[X] += DP[movedX][movedY]를 수행하면 된다. 이대로 수행하게 되면 문제가 발생한다.이미 진행된 경로에 대해서 .. 2024. 8. 16. BOJ 11404 - 플로이드 https://www.acmicpc.net/problem/11404 접근모든 도시끼리 이동하는 비용 최솟값을 구하는 문제이다.시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.따라서, 모든 노드를 거쳐 시작 도시와 도착 도시를 이동하는 모든 노선을 확인해야 한다.이를 구현하기 적합한 알고리즘은 플로이드 와샬이다. 플로이드 와샬을 통해 중간 노드를 거쳐가는 모든 노선을 확인해보도록 하자.알고리즘은 매우 간단하다. 당연하지만, 시작 노드와 도착 노선 그리고 중간 노드를 모두 확인하기에 O(N^3)이 걸린다. 더보기#include #include #include #include using namespace std;#define MAX 9999999int n, m;int res[101][101];v.. 2024. 7. 1. 이전 1 다음
