[C/C++] 코드업(codeup) 4439번 벽장문의 이동

▽문제 바로가기

https://codeup.kr/problem.php?id=4439

벽장문의 이동

---

입력

첫 번째 줄에 벽장의 개수를 나타내는 2보다 크고 20보다 작거나 같은 하나의 정수,

두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수,

그리고 세 번째줄에는 사용할 벽장들의 순서의 길이(최대 20), 그리고 그 다음줄부터 사용할 벽장의 번호가 한줄에 하나씩 순서대로 주어진다.

 

출력

벽장문의 최소 이동횟수를 화면에 출력한다.

 

문제 풀이

 

두 개의 벽장이 벽장문에 가려져있는데 편의상 이 두 개의 공간을 문이라고 하겠습니다.

 

door1, door2라고 한다면 다음 목적지에 door1이 방문하는 경우와 door2가 방문하는 경우가 있습니다. 완전 탐색을 하면서 목적지와 door1, door2 사이의 거리를 절댓값을 구하면 움직이는 이동 횟수입니다.

 

//#include <stdio.h>
#include <iostream>
//#include <cstdlib>

using namespace std;

int n, m;	//입력받을 정수n 
int door1, door2;	//처음에 열려있는 문
int vDoor[21] = {0,};
bool check[21];
int Min = 987654321;

int MIN(int a, int b){
	return a>b? b:a;
}

int abs(int a){
	return a<0? a*-1:a;
}

//백트래킹
void backtracking(int i, int cnt){
	//도착했으면 최소값 비교
	if(i==m){
		Min = MIN(Min, cnt);
		return;
	}
	
	//다음 목적지
	int dest = vDoor[i];

	//door1으로 목적지 방문
	check[i] = true;
	int temp = door1;
	door1 = dest;
	backtracking(i+1, cnt+abs(dest-temp));
	door1 = temp;
	
	//door2로 목적지 방문
	temp = door2;
	door2 = dest;
	backtracking(i+1, cnt+abs(dest-temp));
	door2 = temp;
	
}

int main(){
	
	scanf("%d", &n);
	scanf("%d%d", &door1, &door2);
	
	scanf("%d", &m);
	for(int i=0;i<m;i++){
		scanf("%d", &vDoor[i]);
	}
	
	//백트래킹
	backtracking(0, 0);
	
	printf("%d", Min);
	
	return 0;
}