Construct a Palindrome( Atcoder 196-F )

문제 : https://atcoder.jp/contests/abc197/tasks/abc197_f

F - Construct a Palindrome

 

문제 파악하기

1번 정점부터 시작해서 N번 정점까지 이동하면서 팰린드롬을 만들 수 있는지 없는지, 그리고 만약 만들 수 있다면 그 때의 최소 길이는 얼마인지 찾는 문제입니다. M개의 간선에는 각각 알파벳이 적혀있으며, 경로 상의 간선들에 적힌 알파벳을 나열하면 하나의 문자열이 나옵니다. 이 문자열이 팰린드롬인지, 그리고 만약 팰린드롬이라면 만들 수 있는 최소 길이인지 확인하면 문제를 해결할 수 있습니다.

 

이 문제를 풀기 위해서는 팰린드롬의 개념을 알고 있으면 풀기 쉬워집니다. 그러니 한번 생각해봅시다. 팰린드롬이 뭘까요? 위키피디아를 살펴보면 다음과 같은 설명이 있습니다.

팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열을 의미한다.

 

팰린드롬은 앞뒤가 대칭인 문자열을 의미합니다. 그렇기에 해당 문제열이 팰린드롬인지 확인할 때에는 2개의 변수를 사용하여 대칭을 만족하는지 확인하는 알고리즘을 사용합니다. 그렇다면 지금도 해당 알고리즘을 사용할 수 없을까요? 정답은 사용할 수 있습니다.

 

문제 해결하기

우리는 시작과 종료 정점을 알고 있습니다. 시작은 1번 정점에서, 종료는 N번 정점에서 이루어집니다. 그렇다면 2개의 정점에서 동시에 출발하는건 어떨까요? 하나는 1번 정점에서, 하나는 N번 정점에서 시작해서 서로 동일한 알파벳을 가진 간선이 있다면 해당 간선을 사용하여 이동하면서 탐색을 계속 진행하는 것입니다. 그러다 만약 팰린드롬을 만들 수 있다면 하나의 정점 혹은 간선에서 만날 것이며, 팰린드롬을 만들 수 없다면 탐색은 종료될 것입니다.

 

여기서 중요한 점은 종료 조건입니다. 팰린드롬을 만들 수 없다면 자연스럽게 종료되겠지만 문제는 팰린드롬을 만들 수 있을 경우입니다. 이 경우에는 조건문을 사용하여 따로 구현해야 합니다. 하나의 정점에서 모이는 경우에는 다음 위치가 모두 동일한 정점인 경우이며, 하나의 간선에서 모이는 경우에는 이동할 정점 다음 위치가 현재 위치인 경우입니다. 이 경우를 먼저 확인한 다음에 탐색을 진행하면 됩니다.

 

종료 조건을 만들었다면 문제를 해결할 준비가 어느정도 완료되었습니다. 지금 주어진 테스트케이스를 작동시키면 제대로 작동하겠지만 정점의 개수가 많아진다면 제한시간 안에 해결할 수 없게 됩니다. 그렇기 때문에 불필요한 탐색을 줄이는 방법을 생각해야 합니다. 그 때, 주로 사용하는 방법은 바로 배열을 사용하는 것입니다. 배열을 사용하여 두 개의 정점의 위치를 확인하면서 한 번이라도 방문한 위치라면 탐색하지 않고 넘기면 시간을 효과적으로 줄일 수 있습니다. 이렇게 만들면 우리가 원하는 시간 내 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
#define NMAX 1010
#define INF 0x7FFFFFFF
#define lint long long int
#define PAIR pair<int, char>
using namespace std;
 
struct Pos {
    int st, ed;
    int cnt;
};
 
int N, M, A, B;
int st, ed, cnt;
char c;
 
int ret;
int check[NMAX][NMAX];
vector< PAIR > graph[NMAX];
 
struct cmp {
    bool operator() (Pos a, Pos b) { return a.cnt > b.cnt; }
};
priority_queue< Pos, vector< Pos >, cmp > pq;
 
int main() {
    // 입력
    scanf("%d %d",  &N, &M);
    for(int i=1;i<=M;i++) {
        scanf("%d %d %c", &A, &B, &c);
 
        if(A == B) graph[A].push_back({B, c});
        else {
            graph[A].push_back({B, c});
            graph[B].push_back({A, c});
        }
    }
 
    // BFS
    ret = INF;
    pq.push({1, N, 0});
    while(!pq.empty() and ret == INF) {
        st = pq.top().st;
        ed = pq.top().ed;
        cnt = pq.top().cnt;
        pq.pop();
 
        // 이미 탐색을 한 경우
        if(check[st][ed]) continue;
        else check[st][ed] = 1;
 
        // 다음 위치 탐색
        for(PAIR nxtSt:graph[st]) {
            for(PAIR nxtEd:graph[ed]) {
                // 다음 위치에 갈 수 없는 경우(팰린드롬을 만들지 못 하는 경우)
                if(nxtSt.second != nxtEd.second) continue;
                else {
                    // 맞은편에 있는 경우
                    if(nxtSt.first == ed or nxtEd.first == st) ret = min( ret, cnt+1 );
                    // 다음 위치에서 서로 만나는 경우
                    else if(nxtSt.first == nxtEd.first) ret = min( ret, cnt+2 );
                    // 팰린드롬을 만들 수 있는 경우
                    else pq.push({nxtSt.first, nxtEd.first, cnt+2});
                }
            }
        }
    }
 
    // 출력
    if(ret == INF) printf("-1");
    else printf("%d", ret);
}
 
/*
8 8
1 2 a
2 3 b
1 3 c
3 4 b
4 5 a
5 6 c
6 7 b
7 8 a
ans: 10
 
4 3
1 2 a
2 3 d
3 4 a
ans: 3
*/

후기

그래프와 팰린드롬을 합친 재미있는 문제입니다. 그래프를 직접 그려보면 확실히 해결 방법이 눈에 들어오는 문제입니다. 그래프 탐색을 이용한 심화 문제라고 생각합니다.