티스토리 뷰

반응형

https://www.acmicpc.net/problem/17182

 

17182번: 우주 탐사선

우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위

www.acmicpc.net


⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

  • 그래프 이론
  • 비트마스킹
  • 백트래킹
  • 플로이드-와샬
  • 외판원 순회 문제

 


 

⊙ 문제 접근 과정

 

플로이드 와샬을 이용하여 모든 행성 방문 시 최단거리를 구하는 문제이다.

 

플로이드 와샬에선 문제없이 풀었지만, 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
반응형
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/12   »
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
글 보관함