그래프 균형 맞추기( BOJ 22344 )

문제 : https://www.acmicpc.net/problem/22344

22344번: 그래프 균형 맞추기

 

문제 파악하기

그래프 내 간선의 가중치가 주어질 때, 그래프의 균형을 맞출 수 있는 여러 가지 방법 중 모든 정점 가중치 값의 절댓값 합이 가장 작은 경우를 구하는 문제입니다. 그래프의 균형은 두 정점을 연결하는 간선의 가중치와 두 정점의 가중치의 합이 같은 경우를 의미합니다. 문제 예시 그림과 같이 모든 간선의 가중치 값이 연결된 정점의 합과 일치하는 경우를 의미하며, 균형을 맞출 수 있는 여러 가지 경우 중 모든 정점의 가중치의 절댓값 합이 가장 적은 경우를 구해야 합니다.

 

이 문제를 해결하기 위해서는 우선 2가지 경우로 나누어야 합니다. 첫 번째, 주어진 그래프에 사이클이 있는 경우입니다. 사이클이 있는 경우에는 각각의 정점에 들어가야 하는 값이 고정됩니다. 두 번째, 사이클이 없는 경우입니다. 사이클이 없는 경우에는 정점에 들어갈 수 있는 값이 무수히 많아집니다. 이 때에는 최솟값을 찾아야 합니다. 그렇다면 각각의 경우를 어떻게 구할 수 있는지 살펴봅시다.

 

문제 해결하기

우선, 사이클이 있는 경우에는 모든 정점에 들어갈 수 있는 값이 1가지로 고정됩니다. 어떤 한 정점의 값을 X라고 정의하면, 사이클이 발생했을 때에는 수식을 통해 X의 값을 구할 수 있습니다. 다만, X의 값이 정수로 나온다는 보장이 없기에 모든 탐색을 완료한 다음, 구해진 값이 정수인지 아닌지 확인해야 합니다. 또한, 사이클이 여러 개 있을 수 있기 때문에 각각의 사이클에서 구해진 값을 비교해서 하나라도 다른 경우가 나왔는지 확인할 필요가 있습니다.

 

만약 사이클이 나오지 않았다면 우리는 시작점의 가중치를 X로 놓은 다음, DFS 탐색을 통해 모든 정점의 가중치를 X에 대한 수식으로 나타낼 수 있으며, 모든 정점 가중치의 합은 다음과 같이 표현할 수 있습니다.

f(x) = | x-a | + | x-b | + ... + | x-n |

 

이렇게 절댓값의 합이 최소가 되는 경우는 바로 a ~ n 사이의 값 중 중간값일 때, 합이 최소가 됩니다. 따라서 DFS 탐색을 끝낸 다음에 구해진 a ~ n 값을 정렬하여 중간값을 찾으면 문제를 해결할 수 있습니다. 문제를 해결하는 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#define NMAX 1010
 
int R, C, K;
int x, y, idx;
 
int check[NMAX][NMAX];
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
 
bool safe(int x, int y) {
    if(x<1 or y<1 or x>R or y>C or check[x][y]) return 0;
    else return 1;
}
 
int main() {
    scanf("%d %d", &R, &C);
    scanf("%d", &K);
 
    if(R*C < K) printf("0");
    else {
        x = y = 1;
        idx = 0;
        
        while(1) {
            K--;
            check[x][y] = 1;
            if(!safe(x+dx[idx], y+dy[idx])) idx = (idx+1)%4;
            
            if(K == 0) break;
            else {
                x += dx[idx];
                y += dy[idx];
            }
        }
        
        printf("%d %d", x, y);
    }
}

후기

그래프에 직접 손으로 적어보면 해결 방법이 손쉽게 떠올려지는 문제입니다. 다만, 사이클이 있을 때를 신경쓰는 점과, 모든 정점의 값을 따로 저장하고, 정렬하는 걸 구현하는데 조금은 귀찮은 점이 있었습니다. DFS 탐색을 연습하는 사람이라면 한번 도전할만한 문제라고 생각합니다.