[BOJ] 백준 2666 벽장문의 이동

출처: https://www.acmicpc.net/problem/2666

 Input 

7

2 5

4

3

1

6

5

 

 Output 

5

문제 이해: 미닫이 문으로 구성된 옷장을 연상하면 됩니다.

             벽장문을 최소한으로 움직여서 주어진 순서대로 벽장을 사용을 사용하는 것입니다.

벽장의 문을 움직이면 열려있던 곳은 닫히게 되고, 문이 위치한 곳은 열리게 되는 구조로서

한칸씩 움직일 수 있으므로, 만약 x 위치에서 y위치에 존재하는 문을 사용한다면

▶ 이동 횟수 = abs(x - y)

 

문을 선택하는 경우는 2가지로, 초기에 주어지는 첫번째, 두번째 벽장문을 선택하는 Case

▶ DFS(첫번째 문의 위치, 두번째 문의 위치, 현재 열려는 벽장 위치 순서, 누적 이동 횟수)

---

#include <stdio.h>
 
int N, M, ans;
int use[20];
inline int min(int A, int B) { return A < B ? A : B; }
inline int abs(int x) { return x < 0 ? -x : x; }
 
void DFS(int first, int second, int depth, int moveCnt) {
    // 분기한정
    if (moveCnt > ans) return;
 
    if (depth == M) {
        ans = (ans, moveCnt);
        return;
    }
    DFS(use[depth], second, depth + 1, moveCnt + abs(first - use[depth]));
    DFS(first, use[depth], depth + 1, moveCnt + abs(second - use[depth]));
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    int first, second;
    scanf("%d", &N); // 벽장의 개수
    scanf("%d %d", &first, &second); // 열린 문
    scanf("%d", &M); // 사용 순서
    for (int i = 0; i < M; i++) {
        scanf("%d", &use[i]);
    }
 
    ans = N * M + 1;
    DFS(first, second, 0, 0);
    printf("%d", ans);
}