가중치 그래프 입문

http://koistudy.net/?mid=prob_page&NO=706

-- R&E 가는길 (Tiny)

 

지금까지 우리는 정점과 간선으로만 이루어진 그래프를 탐색하였다. 여기서 가중치가 포함되면 물론 일반적인 DFS/BFS의 형식을 벗어나지는 못하지만, 또 다른 방법으로 그래프를 해석할 수 있게 된다. 오늘은 Back_track을 이용해 가중치 그래프에서 최소 경로로 도착지점에 도착하는 비용을 구해보자.

 

목차

1. 지금가지의 그래프 탐색

2. back_track을 이용한 그래프 탐색과 가중치 처리

 

지금까지의 그래프 탐색

지금까지 그래프 탐색하면 깊이 우선 탐색으로 파고 들어가는 방법을 떠올렸을 것이다. 대표적으로 KOI 문제 중에는 단지 번호 붙이기가 있다. 이러한 것은 그래프 탐색의 한 종류이지만 그 전체는 아니다. 코드를 조금더 파다보면, 유한 오토마타, 그리고 오늘할 가중치 그래프 최소/최대 비용 등의 많은 그래프가 존재한다. 또 DFS 외에도 BFS라는 것이 있는데, BFS는 쉽게 말해서 가까이 있는 것을 우선으로 탐색하는 것이다. 이 이야기를 하는 이유가 뭘까? 기존에 가지고 있던 틀을 조금만 깨면 다른 그래프 문제를 조금더 편하게 받아들일 수 있다. 그럼 서론은 여기까지하고, 본론으로 넘어가 보자.

 

back_track을 이용한 그래프 탐색과 가중치 처리

 - back_track이란?

 값을 찾아서 열심히 갑니다~ 가는 도중에 뭔가 답이 아닌거 같다? 하면 다시 돌아오는 것을 말합니다. 그러면서 최적의 값을 찾아내는 거죠. 이것을 우리는 back_tracking 이라고 부릅니다.

 

오늘 해 볼 것도 뭔가 답이 아닌거 같으면? 다시 그래프를 탐색하는 방법을 사용할 것입니다.

우선 이런 문제를 풀 때 2가지의 입력 방법을 사용할 수 있는데,

1. 인접 리스트를 이용하는 것

2. vector 배열을 이용해 가중치와 함께 pair로 처리해 주는 것

 

vector 배열은 배우면 사용하도록 하고, 오늘은 인접 리스트를 이용해 보자.

 

인접 리스트를 사용하는 방법은? 매우 간단하다!

정점 a에서 b로 가던, 정점 b에서 a로 가던 결국 가중치(w)는 똑같으니까 다음과 같이 입력해 줄 수 있다.

int d[101][101]; // 인접 리스트를 저장할 배열 선언
int main() 
{
    while(1){
        int a, b, w; scanf("%d%d%d", &a, &b, &w);
        d[a][b] = d[b][a] = w; // 정점의 좌표에 가중치를 입력
    }
    ...

 

그런 다음에는 우리가 알던 DFS를 이용해서 그래프를 탐색해 줄 것인데, 탐색하면서 우리가 필요한 정보는 무엇일까?에 대한 고민을 해야 한다. 위 문제의 경우에는 시작할 정점( 1 )과 가중치를 저장할 변수가 필요하다.

 

본격적으로 탐색에 들어가보자.

 

탐색을 어떻게 돌리면 좋을까? 제일 먼저 해야 하는 생각은 이미 갔던 곳을 갈 필요가 있을까? 이다. 이미 갔던 곳을 한번 더 방문하게 되면 최종적으로 쌓인 가중치가 절대 최소가 될 수 없다는 것을 알 수 있다. 원형 트랙을 한번 돈 거리와 두번 돈 거리는 당연히 한 번 돈 것이 더 작다는 것과 같은 논리이다. 이것은 체크 배열을 하나 만들어서 표현이 가능하다.

 

만약 답이 아니라서 back_track해서 돌아왔다면? 이미 한번 간 정점을 다시 방문해도 된다. 서술형 문제를 풀다가 틀리게 푼 것 같은 부분이 나오면 우리가 틀리게 푼 것 같은 곳을 지우고 다시 푸는 것과 같은 원리이다. 이미 맞은 곳은 건들일 필요가 없다는 것이다. 따라서 back_track을 해서 돌아오면 정점의 체크를 풀어준다.

 

마지막으로 처리해 주어야 할 것은 완전히 다 돌았을 때이다. 도착지점에 도착했을 때, 최대보다 작은 가중치의 합이 발견되면 최대를 갱신해주어야 한다. 꼭 이런 경우가 아니더라도 마지막 정점을 방문함과 동시에 해당 진행은 멈춰준다.

 

약간 말장난으로? 표현해 보자면, 서술형 문제를 푸는데, 맞은 문제 또 풀면 의미 없고 맞는 풀이 써 놓고 지우면 낭비니까 틀린 부분만 지우고 다시 풀고 다 풀었으면 답을 체크해 주면 된다. 그렇게 해서 완성된 코드는 다음과 같다.

 

source code - R&E 가는길

#include <bits/stdc++.h>
using namespace std;

int v, d[20][20], M = INT_MAX, ck[20];

void f(int V, int W) {
    if(V == v) {
        if(W < M) M = W;
        return;
    }

    for(int i=1; i<=v; i++)
        if(d[V][i] && !ck[i]) {
            ck[i] = 1;
            f(i, W + d[V][i]);
            ck[i] = 0;
        }
}

int main()
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int e; cin >> v >> e;
    while(e--) {
        int x1, x2, w; cin >> x1 >> x2 >> w;
        d[x1][x2] = d[x2][x1] = w;
    }

    f(1, 0);

    if(M == INT_MAX) {
        cout << "-1\n";
    } else {
        cout << M << "\n";
    }

    return 0;
}

 

이 방법은 그다지 효율적인 방법은 아니지만, 처음 그래프를 입문하는 입장에서는 제일 괜찮은 문제라서 소개해 보았다.

비슷한 문제로 CodeUp에 최단 경로 구하기 라는 문제가 있는데, 꼭 한번 풀어보면 좋을 것 같다. ( 시간초과 나면 정상! )

 

(2021.11.20) 추가 내용

 

백트레킹을 진행하면서 아닌거 같은 값을 날려버리는 방법도 있다. 아이디어는 다음과 같다.

만약 합이 저장된 현재 최소를 넘어버리면? 그 뒤를 연산할 필요가 있을까? 라는 질문을 하게 된다. 이것을 이용해 백트레킹을 하면서 연산을 날려버리면 그만큼 연산량이 줄어든다.

 

최악의 경우 최소가 백트레킹을 통해 연산되는 합이 내림차순 이어서 다 돌려야 하는 경우가 발생할 수 있다. 이런 특수한 경우를 제외하면, 그 외의 경우에는 확실히 연산량 감소에 효과가 있다는 것을 알 수 있다. 코드는 다음과 같다.

 

source code - add on 20211.11.20

void f(int V, int W) {
	if(W > M) return;
    if(V == v) {
        if(W < M) M = W;
        return;
    }

    for(int i=1; i<=v; i++)
        if(d[V][i] && !ck[i]) {
            ck[i] = 1;
            f(i, W + d[V][i]);
            ck[i] = 0;
        }
}