1.
|
#include <stdio.h>
#include <iostream>
using namespace std;
int city[15][15];
int visited[15];
int N;
int Min = 99999999;
int check()
{
for(int i = 1; i < N; i++)
{
if(visited[i] == 0)
{
return 0;
}
}
return 1;
}
void DFS(int sum, int cur)
{
// 1번 ~ N-1번 도시를 모두 방문한 경우
if(check() == 1)
{
// 0번 마을까지의 경로가 존재한다면
if(city[cur][0] != 0)
{
sum += city[cur][0];
if(sum < Min)
{
Min = sum;
}
}
return;
}
for(int i = 1; i < N; i++)
{
if(city[cur][i] != 0 && visited[i] == 0)
{
visited[i] = 1;
DFS(sum + city[cur][i], i);
visited[i] = 0;
}
}
}
int main(void)
{
// freopen("B10971_input.txt", "r", stdin);
scanf("%d", &N);
// 0번 ~ N-1번 도시
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
scanf("%d", &city[i][j]);
}
}
// 0 →1 →2 →3 →4 →0 시작점이 0인 최소비용 루트가 있다고 가정해보자. 이 때 'A원'의 비용이 들었다면,
// 2 →3 →4 →0 →1 →2 시작점이 2인 최소비용 루트는 시작점과 관계없이 'A원'의 비용이 든다.
DFS(0, 0);
cout << Min;
return 0;
}
|
cs |
2.
|
#include <stdio.h>
#include <iostream>
using namespace std;
int city[15][15];
int visited[15];
int N;
int Min = 99999999;
int check()
{
for(int i = 1; i <= N; i++)
{
if(visited[i] == 0)
{
return 0;
}
}
return 1;
}
void DFS(int sum, int start, int arrive)
{
if(check() == 1)
{
// 출발점으로 돌아올때 0이 아닌 조건을 추가해주는것이 중요
if(city[start][arrive] != 0)
{
sum += city[start][arrive];
if(sum < Min)
{
Min = sum;
}
}
return;
}
for(int i = 1; i <= N; i++)
{
if(city[start][i] != 0 && visited[i] == 0)
{
visited[i] = 1;
DFS(sum + city[start][i], i, arrive);
visited[i] = 0;
}
}
}
int main(void)
{
// freopen("B10971_input.txt", "r", stdin);
scanf("%d", &N);
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
{
scanf("%d", &city[i][j]);
}
}
for(int i = 1; i <= N; i++)
{
visited[i] = 1;
DFS(0, i, i);
visited[i] = 0;
}
cout << Min;
return 0;
}
|
cs |
'Baekjoon > DFS' 카테고리의 다른 글
| [백준 2667] 단지번호 붙이기 (DFS) (C/C++) (0) | 2020.01.26 |
|---|---|
| [백준 10451] 순열 사이클 (DFS) (C/C++) (0) | 2020.01.26 |
| [백준 13023] ABCDE (DFS) (C/C++) (0) | 2019.12.08 |
| [백준 14500] 테트로미노 (DFS) (C/C++) (★) (0) | 2019.11.19 |
| [백준 2210] 숫자판 점프 (DFS) (C/C++) (1) | 2019.11.18 |