티스토리 뷰
반응형
https://www.acmicpc.net/problem/17182
⊙ 문제
⊙ 입력
⊙ 출력
⊙ 예제 입출력
⊙ 알고리즘 분류
- 그래프 이론
- 비트마스킹
- 백트래킹
- 플로이드-와샬
- 외판원 순회 문제
⊙ 문제 접근 과정
플로이드 와샬을 이용하여 모든 행성 방문 시 최단거리를 구하는 문제이다.
플로이드 와샬에선 문제없이 풀었지만, dfs 구현하는 부분에서 어려움을 느껴
어흥님의 블로그에서 해당 문제의 dfs 부분을 참고했다.
자세한 건 코드 주석에 적어놨다!
⊙ 문제 풀이
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 11
int N, K, arr[MAX][MAX], result=9999999;
bool visited[MAX];
//idx = 현재 행성
//dist = 현재 행성까지 거리
//planet = 방문한 행성 수
void dfs(int idx, int dist, int planet) {
if (result < dist) return; //최솟값이 아니라면 무시
if (planet == N) { //모든 행성 방문완료 시
result = min(result, dist); //최솟값 갱신
return;
}
for (int i = 0; i < N; i++) {
if (visited[i]) continue; //방문 행성 무시
visited[i] = true; //방문 표시
dfs(i, dist + arr[idx][i], planet + 1); //dfs 탐색
visited[i] = false;
}
}
int main() {
cin >> N >> K;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
cin >> arr[i][j];
visited[K]=true; //시작점 방문 체크
//플로이드 와샬
for(int k=0;k<N;k++) //k = 거쳐가는 노드
for(int i=0;i<N;i++) // i = 출발 노드
for(int j=0; j<N;j++) // j = 도착 노드
if(arr[i][j] > arr[i][k] + arr[k][j]) //더 작은 값
arr[i][j] = arr[i][k] + arr[k][j];
dfs(K,0,1);
cout << result;
}
⊙ 결과
⊙ 마무리
dfs, bfs 자유자재로 구현하면 좋겠다.
좋아요는 로그인하지 않아도 누를 수 있습니다!
728x90
반응형
'백준 온라인 저지 [BOJ] > C++ [CPP]' 카테고리의 다른 글
[백준(BOJ)] 1956번 : 운동 - C++[CPP] (0) | 2021.08.09 |
---|---|
[백준(BOJ)] 2493번 : 탑 - C++[CPP] (0) | 2021.08.07 |
[백준(BOJ)] 5622번 : 다이얼 - C++[CPP] (0) | 2021.08.05 |
[백준(BOJ)] 2490번 : 윷놀이 - C++[CPP] (0) | 2021.08.05 |
[백준(BOJ)] 16234번 : 인구 이동 - C++[CPP] (0) | 2021.08.03 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 쉽게 배우는 자바 프로그래밍
- java
- 답
- 자바
- 풀이
- OS
- C++
- 자바스크립트
- 문자열
- 운영체제
- 연습문제
- 알고리즘
- 백준
- Web
- 프로그래머스
- BFS
- 그리디
- 정답
- py
- 정리
- 쉽게배우는
- 쉽게배우는자바프로그래밍
- 파이썬
- JS
- 구현
- 우종정
- Python
- 해답
- CPP
- 정렬
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
글 보관함