BOJ 10678 · Meeting Time

알고리즘 분류 : 브루트 포스, DFS  

N이 최대 16이므로, DFS를 통해 모든 경로를 만들어서 해결할 수 있다.

• path 에 경로를 입력받고, 인접 리스트로 활용한다. 인접 행렬로 구현해도 무방하다.
• DFS를 통해 모든 경로를 탐색하고 N에 도착하면 이동 거리의 합을 dist 에 추가한다.
• Bessie의 이동 경로와, Elsie의 이동 경로를 모두 구한다.
• 2개의 dist 리스트에서 서로 값을 비교한다. 값이 겹치면서 가장 작은 값을 정답으로 낸다.

---

C++ 소스코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct field {
    int x, d;
};

int n, m;

void dfs(vector<field> path[], vector<int> &dist, int now, int sums) {
    if (now == n-1) {
        dist.push_back(sums);
        return;
    }
    for (auto k : path[now]) {
        int next = k.x, d = k.d;
        dfs(path, dist, next, sums+d);
    }
}

void solve(vector<field> path1[], vector<field> path2[]) {
    vector<int> dist1, dist2;
    dfs(path1, dist1, 0, 0);
    dfs(path2, dist2, 0, 0);
    sort(dist1.begin(), dist1.end());
    for (auto i : dist1) {
        if (find(dist2.begin(), dist2.end(), i) != dist2.end()) {
            printf("%d\n", i);
            return;
        }
    }
    printf("IMPOSSIBLE\n");
}

int main() {
    scanf("%d %d", &n, &m);
    vector<field> path1[n], path2[n];
    for (int i=0; i<m; i++) {
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        path1[a-1].push_back({b-1, c});
        path2[a-1].push_back({b-1, d});
    }
    solve(path1, path2);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
path1 = [[[] for _ in range(n)] for _ in range(n)]
path2 = [[[] for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c, d = map(int, input().split())
    path1[a-1][b-1] = c
    path2[a-1][b-1] = d

def dfs(path, dist, now, sums):
    if now == n-1:
        dist.append(sums)
        return
    for i in range(now+1, n):
        if path[now][i]:
            dfs(path, dist, i, sums+path[now][i])

def solve():
    dist1, dist2 = [], []
    dfs(path1, dist1, 0, 0)
    dfs(path2, dist2, 0, 0)
    dist1.sort()
    for i in dist1:
        if i in dist2:
            print(i)
            return
    print("IMPOSSIBLE")

solve()

---

참고

• 백준 온라인 저지 : BOJ 10678