backtracking 2

문제는 더블릿 25 backtracking에 있는 door입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/door/door.php?pname=door

열린 문 2곳이 있고 앞으로 열어야 하는 문을 열린 문으로 이동하면서 이동한 거리를 카운트합니다.  이 때 이동한 거리가 가장 적은 회수를 구하는 문제입니다.

다음에 열어야 할 문은 열린 문 2군데중 한 군데와 바꿀 수 있습니다.

무조건 가까운 거리와 바꿨다가는 다음 경우의 수에서 더 많은 거리를 이동해야 할 수 있습니다.

이번에 열어야 할 문을 열린 문 2곳 중에 왼쪽문과 바꾼 경우, 오른쪽문과 바꾼 경우를 모두 트리를 타듯이 타고 내려갑니다.

열린 문이 2와 5이고

열어야 할 문이 3 4 6 5 인 경우

첫 번째 문 교체 (2-3왼) (5-3오)

두 번째 문 교체 (2-3왼 3-4왼) (2-3왼 5-4오) (5-3오 2-4왼) (5-3오 3-4오)

세 번째 문 교체 (2-3왼 3-4왼 4-6왼) (2-3왼 5-4오 3-6왼) (5-3오 2-4왼 4-6왼) (5-3오 3-4오 2-6왼) (2-3왼 3-4왼 5-6오) (2-3왼 5-4오 4-6오) (5-3오 2-4왼 3-6오) (5-3오 3-4오 4-6오)

네 번째 문 교체...

이런 경우를 탐색하도록합니다.

재귀 방식을 이용하며 교체한 문과의 거리의 누적, 교체한 문을 바꿔주면서 진행합니다.

더이상 교체할 문이 없으면 종료하며 이 때까지의 누적 회수가 다른 경우의 누적 회수보다 적을 경우 갱신해주면됩니다.