[SWEA] 1247. 최적경로

문제

1247. [S/W 문제해결 응용] 3일차 - 최적 경로
회사에서 출발해서 N명의 고객에게 방문하고 자신의 집으로 돌아간다.
이때 회사 -> N명의 고객 전체 -> 집 의 경로 중 총 이동거리가 가장 짧은 경로를 찾아라.

풀이

1. 좌표와 방문여부를 저장하는 Cord 클래스 생성
2. 회사, 집, 고객들 위치의 좌표를 Cord에 담아 list에 저장
   • list[0] : 회사
   • list[1] : 집
   • list[2] ~ list[N+1] : 고객들의 위치
3. DFS로 하나씩 방문
   • depth == N 이 되면 getMinDistance()를 호출하고 종료 - 4번에서 계속
   • for문으로 방문하지 않은 좌표를 하나씩 방문함.
   • distance에 이동거리를 추가하여(newDistance) 다음 좌표로 이동(재귀)
4. getMinDistance() : 방문거리에 (마지막 위치 ~ 집)이동거리를 추가하고, 가장 짧은 경로라면 갱신
5. 테스트케이스별 출력

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	

	static int N;
	static Cord [] list; // 0 office, 1 home, 2~N+2 : customer
	static int minDistance=987654321;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{	
			minDistance = 987654321;
			N = sc.nextInt();
			list = new Cord[N+2];
			int r, c;
			for (int i=0; i<N+2; i++) {
				r = sc.nextInt();
				c = sc.nextInt();
				list[i] = new Cord(r, c);
			}
			
			DFS(list[0], 0, 0);
			
			System.out.printf("#%d %d\n", test_case, minDistance);
		}
	}
	
	public static void DFS(Cord cur, int distance, int depth) {
		if (depth == N) {
			getMinDistance(cur, distance);
			return;
		} else {
			int newDistance;
			for (int i=2; i<N+2; i++) {
				if (list[i].isVisit) continue;
				
				newDistance = distance + Math.abs(cur.r-list[i].r) + Math.abs(cur.c-list[i].c);
				list[i].isVisit = true;
				DFS(list[i], newDistance, depth+1);
				list[i].isVisit = false;
			}
		}
	}
	
	public static void getMinDistance(Cord last, int distance) {
		distance += Math.abs(list[1].r - last.r) + Math.abs(list[1].c - last.c);
		if (distance < minDistance) {
			minDistance = distance;
		}
	}
	
	static class Cord {
		int r;
		int c;
		boolean isVisit;
		Cord(int r, int c) {
			this.r = r;
			this.c = c;
			this.isVisit = false;
		}
		
	}
	
}

개선

• 전처리 (중복되는 연산 저장)
• 백트래킹