[Algorithm] Baekjoon 2157번 : 여행

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
struct Node
{
    int cityNum;
    int score;
};
 
const int minNum = -0x3f3f3f3f;
int n, m, k;
vector<vector<Node>> graph(301);
int dp[301][301] = { 0 };
 
int DFS(int cityNum, int count)
{
    int& result = dp[cityNum][count];
    if (result != -1) return result; 
 
    if (cityNum == n)
    {
        if (count <= m)
        {
            return 0;
        }
        else
        {
            return minNum;
        }
    }
 
    result = minNum;
    for (int i = 0; i < graph[cityNum].size(); ++i)
    {
        int nextCity = graph[cityNum][i].cityNum;
        int nextScore = graph[cityNum][i].score;
 
        if (nextCity < cityNum) continue;
 
        int temp = DFS(nextCity, count+1);
        if (temp == minNum) continue; // 유효하지않은 경로이면
 
        result = max(result, temp + nextScore);
    }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < k; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(1, 1);
}
 
 

 

 

이 문제가 정답률이 낮은 이유는, '해당 경로가 유효하지 않다' 와, '해당 경로는 아직 탐색하지 않았다'를 구분하지 않고 푸는 경우가 많았기 때문일거라 생각한다.

처음에 dp테이블을 -1로 초기화함으로써 아직 탐색하지않았다고 표시를 해줘야 한다.

이후 탐색을 할 때, 목표 n번도시에 도착했는데 count가 m을 초과할 경우, minNum을 리턴시켜서 탐색은 했되, 유효하지않은 경로라는것을 알려줘야 한다.