당일치기 전주 여행 (백트래킹)

 

A1: 당일치기 전주 여행 1

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
	int hh,mm,h,m;
	vector<vector<int>> arr(6);
	vector<int> gone; // 아직 안 간 곳 저장 
	scanf("%2d:%2d",&hh,&mm);
	scanf("%2d:%2d",&h,&m);
	
	for(int i=0; i<6; i++){
		for(int j=0; j<6; j++){
			int temp;
			cin >> temp;
			arr[i].push_back(temp);
		}
	}
	
	// [0,0] [0,1]
	// [1,0] ...
	// [2,0] ...
	
	int sum=0;
	int line=0;
	int temp;
	
	//0번째 줄부터 돌면서 최솟값을 찾음 
	//이때 최솟값의 인덱스가 line이거나, 이미 갔거나, 0이면 안됨.
	//최솟값을 sum에 더하고 line을 (현재 line 최솟값의 인덱스)로 함 
	
	//그 라인으로 이동해서 최솟값을 찾음(index가 line, 0, 이미 갔던곳이면 안됨)
	// 최솟값을 sum에 더하고 line을 (현재 line 최솟값의 인덱스)로 함
	
	//반복하다가 마지막 남은 line에 도착하면 종료.
	//종료 후 그 line의 0번째 인덱스 값을 sum에 더함
	
	while(gone.size()<5){
		int min = 21; //이동시간이 20분 이하 
		
		for(int i=1; i<6; i++){ //0은 생각안함 
 			if(i!=line && count(gone.begin(),gone.end(),i)==0 && min>arr[line][i]){
 				 min = arr[line][i];
 				 temp = i;
			 }
		}
		line = temp;
		sum+=min;
		gone.push_back(temp); //gone 배열에 간 곳 추가
		if(sum<0) return 0;	
	}
	sum += arr[line][0];
	
	//cout << sum << "\n";
	
	int time = (h*60+m) - (hh*60+mm) - sum;
	printf("%02d:%02d",time/60,time%60);
	
    return 0;
}

 

이렇게 코드를 짰었는데 테스트케이스 2와 답이 달랐다...

 

그래서 대회가 끝나고 정답지를 보니 5중 for문으로 모든 경우의 값들을 구해서 그 중 최솟값을 찾았었다.

범위가 크지 않을 땐 이런 식으로 풀어도 되겠다는 생각을 했다.

//2023 전북 SFPC A1 예제 코드
//https://drive.google.com/drive/folders/1LYvmdVuvezMZdvL-994Fkqwk45AEIEYr

#include<bits/stdc++.h>
using namespace std;
int A[6][6], B[6];
int main(){
	int h1, h2, m1, m2, t, i, j,i1,i2,i3,i4,i5, min1=24*60+10;
	scanf("%d:%d", &h1, &m1);
	scanf("%d:%d", &h2, &m2);
	t = h2*60+m2-h1*60-m1;
	for(i=0;i<6;i++){
		for(j=0;j<6;j++){
			scanf("%d", &A[i][j]);
		}
	}
	for(i1=1;i1<=5;i1++){
		for(i2=1;i2<=5;i2++){
			for(i3=1;i3<=5;i3++){
				for(i4=1;i4<=5;i4++){
					for(i5=1;i5<=5;i5++){
						if(i1!=i2 and i1!=i3 and i1!=i4 and i1!=i5 and i2!=i3 and i2!=i4 and i2!=i5 and i3!=i4 and i3!=i5 and i4!=i5){
							if(A[0][i1]+A[i1][i2]+A[i2][i3]+A[i3][i4]+A[i4][i5]+A[i5][0] < min1){
								min1 = A[0][i1]+A[i1][i2]+A[i2][i3]+A[i3][i4]+A[i4][i5]+A[i5][0];
							}
						}
					}
				}
			}
		}
	}
	t = t - min1;
	printf("%02d:%02d", t/60,t%60);
}

---

백트래킹을 배운 뒤에 이 문제는 백트래킹으로 풀 수 있을 것 같다고 생각하여 다시 풀어보았다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<vector<int>> input(6);
int arr[10];
int num[10];
bool isused[10];
int Min = 9999999;

void func(int k){
	if(k==6){
		int sum=0;
		for(int i=0;i<=4;i++){
			sum+=input[arr[i]][arr[i+1]];
		}
		sum+=input[arr[5]][0];
		if(sum<Min) Min=sum;
		return;
	}
	
	for(int i=1;i<=5;i++){
		if(!isused[i]){
			isused[i] = true;
			arr[k] = i;
 			func(k+1);
			isused[i] = false;
		}
	}
}

int main() {
	int hh,mm,h,m;
	scanf("%2d:%2d",&hh,&mm);
	scanf("%2d:%2d",&h,&m);
	
	for(int i=0; i<6; i++){
		for(int j=0; j<6; j++){
			int temp;
			cin >> temp;
			input[i].push_back(temp);
		}
	}
	
	func(1);

	int time = (h*60+m) - (hh*60+mm) - Min;
	printf("%02d:%02d",time/60,time%60);
	
    return 0;
}

위 코드와 동작은 같지만 개인적으로 5중 for문보다는 맘에 드는 코드다.