[백준 31871][DFS] 영일랜드

출제 배경

한양대 에리카 알고리즘 대회인 HEPC 2024에서 본인이 출제한 문제이다. 본래 N이 16인 비트마스킹 DP 문제였으나, 대회의 전체적인 난이도가 너무 높다는 이유로 n만 줄여서... DFS로 풀 수 있는 문제가 되었다. 출제 이후 약 3개월이 지난 지금 실버 2에 위치해있다. 사실, 예상 난이도가 실버 4~5였는데 생각보다 높게 측정돼 있어서 또 억까 당한 느낌이다. (우주비행사 정민..)

 

 

문제 설명

문제 링크

 

요약하자면, 단방향 그래프에서 모든 노드를 한 번씩만 방문하고 돌아오는, 그냥 외판원 순회 문제이다(아무래도 출제 배경이..) 다만 최장 시간을 구해야하고, 두 노드를 연결하는 단방향 간선이 여러 개일 수도 있으며, 모든 노드를 한 번씩만 방문하고 돌아오는 경로가 존재하지 않을 수 있다는 점만 처리해주면 쉽게 풀 수 있다.

 

N이 최대 9, 정문까지 포함해 노드가 최대 10개이므로 DFS로 풀 수 있다. 여기서 일반적인 DFS를 사용하기 위해, 입력 과정에서 같은 단방향 간선 입력 중 가장 시간이 오래 걸리는 간선만을 저장하여 쉽게 풀어낼 수 있다.

 

여타 DFS와 같게 방문 배열을 사용하며, 탐색이 완료되면 방문을 지워준다.  DFS로 모든 노드를 방문하는 경로를 찾으면, 기존 찾았던 경로의 최대 시간과 비교하여 더 크다면 시간을 갱신해준다.

 

DFS가 완료되면 찾은 가장 큰 시간을 출력하고, 만약 그러한 경로를 찾지 못했다면 -1을 출력하면 된다.

 

코드

#include <iostream>
#include <queue>
using namespace std;

int n, m, arr[11][11], ans = -1;
bool visited[11];

void dfs(int state, int dis, int cnt)
{
    if (cnt == n)
    {
        if (arr[state][0] > 0)
        {
            ans = max(ans, dis + arr[state][0]);
        }
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i] && arr[state][i] > 0)
        {
            visited[i] = true;
            dfs(i, dis + arr[state][i], cnt + 1);
            visited[i] = false;
        }
    }
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int ti, tj, d;
        cin >> ti >> tj >> d;
        if (ti == tj)
            continue;
        arr[ti][tj] = max(arr[ti][tj], d);
    }
    dfs(0, 0, 0);
    cout << ans;
}