C1: [LAB] 지하철-SPJ

문제 설명 

지방에서 서울에 관광 온 성수는 지하철 노선을 보고 깜짝 놀랐다. 노선이 엄청나게 복잡하기 때문이었다. 각 노선들이 서로 얽혀있어서 잘못하면 10분도 안 걸리는 거리를 1시간 동안 갈 수도 있는 상황이었다. 어쩔 수 없이 성수는 현재 숙소에서 관광할 목적지까지 가장 짧은 시간에 도착할 수 있는 경로와 시간을 표로 만들려고 한다.

 

단, 각 지하철역에서 관광지가 있고, 지하철을 갈아타는데 소요되는 시간은 없다고 가정한다.

---

* 입출력 Template이 필요한 경우 C 제출은 다음 코드를 복사하여 코드를 작성하시오.

#include <stdio.h>
#define MAXN (100)
int N, M;//지하철역수, 목적역
int S[MAXN+2][MAXN+2];//[s][e]=시간

void InputData(void){
	scanf("%d %d", &N, &M);
	for (int s=1; s<=N; s++){
		for (int e=1; e<=N; e++){
			scanf("%d", &S[s][e]);
		}
	}
}

int main(void){
	InputData();//입력

	//여기서부터 작성
	return 0;
}

---

* 입출력 Template이 필요한 경우 C++ 제출은 다음 코드를 복사하여 코드를 작성하시오.

#include <iostream>
using namespace std;
#define MAXN (100)
int N, M;//지하철역수, 목적역
int S[MAXN+2][MAXN+2];//[s][e]=시간

void InputData(){
	cin >> N >> M;
	for (int s=1; s<=N; s++){
		for (int e=1; e<=N; e++){
			cin >> S[s][e];
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	InputData();//입력

	//여기서부터 작성
	return 0;
}

---

* 입출력 Template이 필요한 경우 Java 제출은 다음 코드를 복사하여 코드를 작성하시오.

import java.io.*;
import java.util.*;
public class Main {
	int N, M;//지하철역수, 목적역
	int S[][];//[s][e]=시간
	BufferedWriter bw;

	void InputData() throws IOException{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String s[] = bf.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		S = new int[N+1][N+1];
		for (int i=1; i<=N; i++){
			s = bf.readLine().split(" ");
			for (int j=1; j<=N; j++){
				S[i][j] = Integer.parseInt(s[j-1]);
			}
		}
		bf.close();
	}

	public static void main(String[] args) throws IOException {
		Main m = new Main();
		m.bw = new BufferedWriter(new OutputStreamWriter(System.out));
		m.InputData();//입력

		//여기서부터 작성

		m.bw.flush();
		m.bw.close();
	}
}

---

* 입력 Template이 필요한 경우 Python 제출은 다음 코드를 복사하여 코드를 작성하시오.

import sys

def Input_Data():
    readl = sys.stdin.readline
    N, M = map(int,readl().split())
    matrix = [[0] * (N+1) if n == 0 else [0]+list(map(int,readl().split())) for n in range(N+1)]
    return N, M, matrix


#입력받는 부분
N, M, matrix = Input_Data()

 

입력 설명 

첫 줄에 N(3<= N <= 100), M(1<= M <= N)을 입력 받는다. N은 지하철역의 수, M은 원하는 목적역의 번호를 입력 받는다.

 

둘째 줄부터 N개의 줄이 나오고, 각 줄에는 N개의 수 S가 입력된다.

 

i번째 줄에서 j번째 수 Sij는 i번 역에서 j번 역까지 가는데 걸리는 시간이다. 1번 역이 숙소가 있는 역이고, Sij에서 i=j 일 때는 항상 0이다. (0<= S <=100)

출력 설명 

목적 역까지 가는데 걸리는 최소 시간과 최소시간으로 가는 최단 경로를 출력한다.

입력 예시 

5 5
0 2 2 5 9
2 0 3 4 8
2 3 0 7 6
5 4 7 0 5
9 5 6 5 0

출력 예시 

8
1 3 5 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAXN (100)
int N, M;//지하철역수, 목적역
int S[MAXN + 2][MAXN + 2];//[s][e]=시간
int visit[MAXN + 10]; //방문정보
int path[MAXN + 10]; //방문 경로
int final_path[MAXN + 10]; //최종확정 경로

void InputData(void) {
	scanf("%d %d", &N, &M);
	for (int s = 1; s <= N; s++) {
		for (int e = 1; e <= N; e++) {
			scanf("%d", &S[s][e]);
		}
	}
}

int min = 1 << 30;

void DFS(int n, int start, int dis)
{
	if (dis >= min) return;
	if (start == M)
	{
		if (min > dis)
		{
			min = dis;
			for (int i = 0; i <= N; i++)
			{
				final_path[i] = path[i];
			}
		}
		return;
	}

	if (n >= N) return;

	for(int i = 2; i <= N; i++)
	{
		if (visit[i] == 1) continue;
		visit[i] = 1;
		path[n] = i;
	
		DFS(n + 1, i, dis + S[start][i]);
		path[n] = 0;
		visit[i] = 0;
	}
	return;
}


int solve()
{
	visit[1] = 1;
	path[0] = 1;
	DFS(1, 1, 0);
	return min;
}


int main(void) {
	InputData();//입력
	int ans = -1;
	//여기서부터 작성
	ans = solve();
	int count = 0;

	printf("%d\n", ans);
	for (int i = 0; i < N; i++)
	{
		if (final_path[i] > 0) count++;
	}

	for (int i = 0; i < count; i++)
	{
		printf("%d ", final_path[i]);
	}

	return 0;
}