[Java/SWEA/백트래킹] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로

문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE&problemTitle=1247&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

 

문제 조건을 보면 집 → N명의 고객 → 회사 경로로 간다.

처음에 최단경로 라는 키워드를 보고서 BFS를 이용해야 하나 싶긴 했었다.

이렇게 하면 N명의 고객을 거치도록 하기 힘들다. 바로 집에서 회사로 가버린다..

 

다음으로 생각한 풀이 방법은 백트래킹이다.

내가 생각하는 백트래킹은

DFS + 가지치기

이다.

 

따라서 기존 DFS를 이용한 순열을 이용해서 고객 순서를 정하면서 거리를 구한다.

 

이 때 가지치기를 하는지, 안하는지에 따라 실행 속도가 크게 차이난다.

이 코드에서는 파라미터로 그때그때 거리를 계산하고, 함수가 재귀호출될 때마다 (전 경로에서 구해둔 min) < distance가 되면 바로 리턴시켰다.

 

이렇게 하면 실행시간을 약 5배 정도 단축할 수 있다.

 

위 : 가지치기 O / 아래 : 가지치기 X

 

 

코드

 

package swea;

import java.io.*;
import java.util.StringTokenizer;

class Node {
	int x;
	int y;

	public Node(int y, int x) {
		this.y = y;
		this.x = x;
	}
}

public class SWEA1247 {

	static StringBuilder sb = new StringBuilder();
	static Node company;
	static Node house;
	static Node[] customers;
	static int min;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) {
			int n = Integer.parseInt(br.readLine());
			customers = new Node[n];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			house = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			company = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

			for (int i = 0; i < n; i++) {
				customers[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			min = Integer.MAX_VALUE;
			makePermutation(n, 0, new Node[n], new boolean[n], 0);

			sb.append("#").append(t).append(" ").append(min).append("\n");
		}
		System.out.print(sb);

		br.close();
	}

	private static void makePermutation(int n, int cnt, Node[] order, boolean[] visited, int distance) {
		if(distance > min)
			return;
		
		if (cnt == n) {
			int result = distance + Math.abs(company.y - order[n - 1].y) + Math.abs(company.x - order[n - 1].x);
			min = Math.min(result, min);
			return;
		}

		for (int i = 0; i < n; i++) {
			if (visited[i])
				continue;

			visited[i] = true;
			order[cnt] = customers[i];
			if (cnt == 0)
				makePermutation(n, cnt + 1, order, visited,
						distance + Math.abs(house.y - order[cnt].y) + Math.abs(house.x - order[cnt].x));
			else
				makePermutation(n, cnt + 1, order, visited, distance + Math.abs(order[cnt - 1].y - order[cnt].y)
						+ Math.abs(order[cnt - 1].x - order[cnt].x));
			visited[i] = false;
		}

	}
}