[1259번] 금속막대

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18NaZqIt8CFAZN

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

n제한은 20인 테스트케이스이다.

BFS를 통해 나사의 위치를 찾아준다.

노드는 현재 나사 인덱스(screw), n제한이 20이니 비트마스크를 이용한 visit관리, 현재 누적 방문 노드 수 cnt를 둔다.

이때 경로를 추적해줘야 하는데 BFS를 통해 자식->부모 경로를 만들 수 있고

마지막에 모두 방문했을 때 역으로 뒤집어주면 정답을 구할 수 있다.

소스 코드 : 

#include <iostream>
 
struct PAIR {
    int front, rear;
};
struct INFO {
    int screw;
    int visit, cnt;
};
int parent[22];
PAIR arr[22];
INFO q[10002];
int first, last;
int n;
int trace[22];
 
void init() {
    first = last = 0;
    for (int i = 0; i < 22; i++)
        parent[i] = i;
}
int main() {
    //freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        init();
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++)
            scanf("%d %d", &arr[i].front, &arr[i].rear);
 
        for (int i = 0; i < n; i++) {
            q[last++] = { i, (1 << i), 1 };
        }
        while (first < last) {
            int screw = q[first].screw;
            int visit = q[first].visit;
            int cnt = q[first++].cnt;
 
            if (((1 << n) - 1) == visit) {
                printf("#%d ", tc);
                first = last = 0;
 
                for (int i = screw, tIdx = 0; ; i = parent[i]) {
                    trace[tIdx++] = i;
                    if (i == parent[i])
                        break;
                }
                for (int i = cnt - 1; i >= 0; i--)
                    printf("%d %d ", arr[trace[i]].front, arr[trace[i]].rear);
                printf("\n");
            }
            for (int i = 0; i < n; i++) {
                if ((1 << i) & visit)
                    continue;
 
                if (arr[screw].rear == arr[i].front) {
                    parent[i] = screw;
                    q[last++] = { i, (visit | (1 << i)), cnt + 1 };
                }
            }
        }
    }
    return 0;
}