[SWEA] 1259 금속막대

출처: SWEA

Approach

Input Data로 주어지는 N이 명확하게 주어지지 않은 문제이다.

그렇기에 N 의 최대값에 따라 배열 크기 설정을 해야 하는데

"input.txt"에 있는 Test Case 중 가장 큰 값으로 제출했는데 문제가 없었다.

 

문제에서 명시하지 않은 조건 중 고려해볼 수 있는 조건은 크게 2가지이다.

- 수나사 값끼리 중복이 없다.

  마찬가지로 암나사끼리도 중복이 없다.

- 연결해서 최대 길이를 구했을 때, 남는 나사가 없다.

    즉, 모든 남사를 연결했다고 볼 수 있다.

 

순열과 조합  

순열과 조합 (백준 N과 M 시리즈)

---

STL Ver.

#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 20 + 2;
int N, TC, xx, xy;
vector<pair<int, int>> screw;
vector<int> ans;
bool chk[MAX_N];

void DFS(vector<int> v) {
       for (int i = 0; i < N; i++) {
              // 아직 선택되지 않은 나사
              if (!chk[i]) {
                     // 암수 조건이 부합되는 경우
                     if (screw[v.back()].second == screw[i].first) {
                           chk[i] = true;
                           v.push_back(i);
                           DFS(v);
                           v.pop_back();
                     }
              }
       }
       // 연결된 나사들 중 가장 긴 길이만 ans[]에 저장
       // 문제 조건상 가장 길게 연결되었을 때, 모든 나사 사용
       if (v.size() > ans.size()) {
              ans.clear();
              for (int i = 0; i < v.size(); i++) {
                     ans.push_back(v[i]);
              }
       }
}

int main() {
       // freopen("input.txt", "r", stdin);
       scanf("%d", &TC);
       for (int tc = 1; tc <= TC; tc++) {
              screw.clear(); ans.clear();
              scanf("%d", &N);
              for (int i = 0; i < N; i++) {
                     scanf("%d %d", &xx, &xy);
                     screw.push_back({ xx, xy });
              }
              // 제일 처음 기준이 되는 나사를 설정
              for (int i = 0; i < N; i++) {
                     // 기준을 잡을 때마다 chk[] 초기화
                     for (int j = 0; j < MAX_N; ++j)
                     {
                           chk[j] = false;
                     }
                     // 기준 선택
                     chk[i] = true;
                     // 해당 기준을 가지고 DFS 탐색
                     vector<int> v;
                     v.push_back(i);
                     DFS(v);
              }
              // 가장 길게 연결된 경우 출력
              printf("#%d ", tc);
              for (int i = 0; i < ans.size(); i++) {
                     printf("%d %d ", screw[ans[i]].first, screw[ans[i]].second);
              }
              printf("\n");
       }
       return 0;
}

 

직접 구현 Ver.

#include<stdio.h>
const int MAX_N = 20 + 2;

struct Screw {
    int xx, xy;
}screw[MAX_N];
int N, TC;
bool visited[MAX_N];
int order[MAX_N];

void input()
{
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &screw[i].xx, &screw[i].xy);
        visited[i] = false;
        order[i] = -1;
    }
}

void DFS(int idx, int cnt) {
    // 모든 나사 사용
    if (idx == N) {
        for (int i = 0; i < N; i++) {
            if (order[i] != -1) {
                printf("%d %d ", screw[order[i]].xx, screw[order[i]].xy);
            }
        }
        return;
    }

    // 임의의 나사를 기준점으로 DFS 탐색 시작
    if (idx == 0) {
        for (int i = 0; i < N; i++) {
            order[idx] = i; visited[i] = true;
            DFS(idx + 1, cnt + 1);
            order[idx] = -1; visited[i] = false;
        }
    }
    
    else {
        for (int i = 0; i < N; i++) {
            // 이미 선택한 나사인 경우
            if (visited[i])
                continue;

            // 암수 조건이 되지 않는 경우
            if (screw[order[idx - 1]].xy != screw[i].xx)
                continue;

            order[idx] = i; visited[i] = true;
            DFS(idx + 1, cnt + 1);
            order[idx] = -1; visited[i] = false;
            
        }
    }
}

void output(int tc) 
{
    printf("#%d ", tc);
    DFS(0, 0);
    printf("\n");
}

int main()
{
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; ++tc)
    {
        scanf("%d", &N);
        input();
        output(tc);
    }
    return 0;
}