[SWEA] - 최적 경로 / 1247번 (Java)

[SWEA] - 최적 경로 / 1247번 (Java)

1. 문제 접근

회사에서 출발해서 모든 고객의 집을 방문하고 자신의 집까지 도달하는 최단 경로를 구하면 되는 문제다.

 

이 때, 시작지점은 회사로, 종료지점은 집으로 고정되어있다는 것을 인지해야한다.

 

시작지점과 종료지점을 고정해두면, N명 고객의 집을 방문하는 순서만 고려하여 방문하면된다.

 

고객의 수`N`은 최대 10이라는 조건을 통해 완전 탐색(순열)을 이용한 풀이를 떠올렸다.

 

하지만, 10! = 3,628,800으로 완전 탐색을 돌려도 되지만, 백트래킹을 통해 시간복잡도를 최적화 할 수 있을 것 같다는 생각이 들었다.

 

백트래킹의 Pruning할 수 있는 경우를 생각해보면, n번째 순열을 구성하며 현재 위치(고객의 집)까지 도달하는 거리가 n-1번째 순열을 구성하며 얻게된 최소거리를 넘게 되는 순간이 pruning을 할 수 있는 조건이 된다.

 

// 현재까지의 거리가 이전까지 계산한 거리보다 길 경우 pruning
if (currDist > minDist) {
	return;
}

 

만일 순열을 모두 구성하였다면(N!) 이는 기저조건이 되며 최단 거리가 될 수 있는 가능성, 즉 유망성이 있는 경우이다.

 

따라서 최종 고객의 집에서부터 나의 집까지의 거리를 최종적으로 더한 뒤 현재까지 계산한 최소거리와 비교하여 최소 거리를 갱신한다.

// 기저조건
if (selectedIdx == N) {
    // 마지막 고객의 집에서부터 집까지의 거리를 최종적으로 계산
    int tempDist = currDist + getDist(currPos, homePos);
    minDist = Math.min(tempDist, minDist);
    return;
}

---

2. 코드

package swea;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 최적 경로
 * @author JinHxxxxKim
 * 
 * 1. 전체 테스트케이스의 수(TC)를 입력받는다.
 * 2. 첫째 줄에는 고객의 수 (N)를 입력받는다.
 * 3. 회사의 좌표,집의 좌표, N명의 고객의 좌표를 차례로 입력받는다.
 * 
 * 시작점 = 회사, 끝점 = 집 고정
 * 
 * 그 사이의 최대 10개의 고객의 집을 순서대로 줄세우는 방법 중에 최소 경로를 찾으면 된다.
 * 다음에 방문할 고객의 집을 결정하게 되면, 현재까지의 거리가 이전에 계산한 거리의 합보다 길다면 종료한다(Pruning)
 * 
 */
public class Sol_1247 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;
	
	private static int N; // 고객 집의 개수
	private static Pos[] selected; // 선택된 배열
	private static boolean[] isSelected; // 선택 여부 배열
	private static Pos[] clientPos; // 고객 위치 배열
	private static Pos companyPos; // 회사 위치
	private static Pos homePos; // 집 위치
	private static int minDist; // 최소 거리
	
	public static void main(String[] args) throws Exception {
		int TC = Integer.parseInt(br.readLine().trim());
		for (int testCase = 1; testCase <= TC; testCase++) {
			// 고객의 수 입력
			N = Integer.parseInt(br.readLine().trim());
			st = new StringTokenizer(br.readLine().trim());
			
			clientPos = new Pos[N];
			
			// 출발점(회사 위치)입력
			companyPos = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			// 끝점(집 위치)입력
			homePos = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			// 고객위치 입력
			for (int clientCnt = 0; clientCnt < N; ++clientCnt) {
				clientPos[clientCnt] = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			minDist = Integer.MAX_VALUE;
			isSelected = new boolean[N];
			selected = new Pos[N];
			// 현재 위치, 현재까지 선택한 고객의 집 개수, 현재까지 거리
			permutaion(companyPos, 0, 0);
			sb.append(String.format("#%d %d\n", testCase, minDist));
		}
		System.out.println(sb);
	}

	private static void permutaion(Pos currPos, int selectedIdx, int currDist) {
		// 기저조건
		if (selectedIdx == N) {
			// 마지막 고객의 집에서부터 집까지의 거리를 최종적으로 계산
			int tempDist = currDist + getDist(currPos, homePos);
			minDist = Math.min(tempDist, minDist);
			return;
		}
		if (currDist > minDist) {
			return;
		}

		for (int elementIdx = 0; elementIdx < N; ++elementIdx) {
			if (isSelected[elementIdx])
				continue;
			// 전처리
			isSelected[elementIdx] = true;
			selected[selectedIdx] = clientPos[elementIdx];
			// 재귀
			permutaion(clientPos[elementIdx], selectedIdx + 1, currDist + getDist(currPos, clientPos[elementIdx]));
			// 후처리
			isSelected[elementIdx] = false;
		}
	}

	// 두 점의 거리를 구하는 메소드
	private static int getDist(Pos currPos, Pos destPos) {
		int dist = 0;
		dist += Math.abs(currPos.xPos - destPos.xPos);
		dist += Math.abs(currPos.yPos - destPos.yPos);
		return dist;
	}

	// 좌표 클래스
	static class Pos{
		int xPos;
		int yPos;
		
		public Pos(int xPos, int yPos) {
			super();
			this.xPos = xPos;
			this.yPos = yPos;
		}
	}
}

---

3. 디버깅

" 회사의 좌표,집의 좌표, N명의 고객의 좌표가 차례로 나열된다."

 

문제 입력 내용에 회사좌표, 집의 좌표, 고객 집의 좌표 순서로 주어진다고 명시되어있다.

 

문제를 주의깊게 읽지 않고 회사좌표, 고객 집의 좌표, 집의 좌표의 순서로 입력받는다고 판단하고 구현했다가 불필요한 디버깅에 시간을 소모했다.

 

문제 입력 조건에 대해 더 주의 깊게 읽어야겠다.

---

4. 결과