||문제 이해
각 그래프를 한번씩 방문할 때 최소 거리를 구하여라.
||해결 계획
n개의 그래프를 한번씩 순회하는 경우의 수는 n! 이다.
그중 가장 최소거리를 지니는 단 하나의 답을 구하는 최적화 문제이다.
다른 방법도 있지만 가장 기초적인 방법 완전 탐색이 있겠다.
||계획 검증
문제에서 그래프의 최대 개수는 8개이다.
그럼 재귀를 8!번 실행해야 하는데
8! = 40320 이므로 O(40320)으로 충분히 실행할 수 있다.
||오답 원인
초기화 해야할 변수는 초기화 하지 않고
초기화를 안해도 되는 변수는 초기화를 해버려서 오답처리를 두번 당했다ㅠ
조심좀 하자ㅠ
||구현
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
int C, N;
double ret;
bool check[10];
double m[10][10];
//idx : 현재 있는 나라
//temp : 중간 결과 값
//cnt : 방문한 나라, 처음에 1을 넣어 시작한다.
void Count(int idx, double temp, int cnt)
{
//기저 사례
if (cnt == N)
{
ret = min(ret, temp);
return;
}
//1.방문하지 않은 나라를 모두 탐색
check[idx] = true;
for (int i = 0; i < N; ++i)
{
//1-1. 방문하지 않은 나라여야하고, 현재나라가 아니어야한다.
if (check[i] == false && i != idx)
{
check[i] = true;
Count(i, temp + m[idx][i], cnt + 1);
check[i] = false;
}
}
check[idx] = false;
}
int main()
{
cout << fixed << setprecision(10);
cin >> C;
while (C--)
{
//1. input,init value
cin >> N;
ret = 1.7976931348623158e+308;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> m[i][j];
}
}
//2. Calculate
for (int i = 0; i < N; ++i)
{
Count(i, 0.0, 1);
}
cout << ret << endl;
}
return 0;
}||되돌아보기
이번에 좀 다시 짚고 넘어가야한건 output formating이다.
분명 double을 사용했는데 알아서 반올림이 되어 출력이 되었다.
그래서 생각난게 output formating인데 오래전에 공부해서 기억이 잘 안나 찾아봤다 =~=;
fixed가 있는 setprecision은 소수부 기준으로 몇자리까지 보여줄 것인가를 의미하기 때문에 사용하였고
한번만 사용해주어도 뒤에 계속 유지되기에 앞에 사용했다.
'코딩 테스트 > 알고리즘 풀이' 카테고리의 다른 글
| [백준 - 15685] 드래곤 커브 (0) | 2022.12.06 |
|---|---|
| [종만북] 수열의 빠른 합 (0) | 2022.12.06 |
| [백준 - 1560] 비숍 (0) | 2022.12.03 |
| [알고스팟 - PICNIC] 소풍 (0) | 2022.12.02 |
| [프로그래머스] 신규 아이디 추천 (0) | 2022.09.16 |
