[SW 1247] 최적 경로

[문제 바로가기]👇

SW Expert Academy

 

💡풀이💡

문제에서 알 수 있는 정보

고객의 집을 어떤 순서로 방문 하느냐에 따라 총 거리가 달라짐
모든 고객의 집을 방문해야 함!
>> nPn 순열!

 

1. 입력 받기

순열을 만들기 위해 사용했는지 확인할 boolean 1차원 배열과

회사 정보, 집 정보, 각 고객 집 정보를 저장할 배열 생성

	static int N;
	static boolean[] v;
	
	static int[] company, home;
	static int[][] customer;
	static int min;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			company = new int[]{r, c}; // 회사 정보 입력
			
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			home = new int[]{r, c}; // 집 정보 입력
			
			customer = new int[N][2]; // 각 고객 정보 입력
			for(int i=0; i<N; i++) {
				r = Integer.parseInt(st.nextToken());
				c = Integer.parseInt(st.nextToken());
				
				customer[i][0] = r;
				customer[i][1] = c;
			}
		}
	}

 

2. 순열 구하기

회사 - 각 고객 집 - 집으로 순으로 거기를 더해가기 때문에 화려한 파라미터를 이용

현재 위치의 좌표(회사/고객 집/ 집) , 지금까지의 거리, cnt를 매개변수로 전달

• 따로 순열을 저장하지 않고 다음으로 넘어갈 때마다 거리를 더해서 넘김
• 최소값보다 이미 지금까지의 거리가 더 크면 더 볼 필요 없기 때문에 return

순열이 완성 되었을 때 마지막으로 집 까지의 거리를 더해줘야 하기 때문에 집까지의 거리 더하기

static void perm(int cnt, int r, int c, int dis) {
	if(dis > min) return;
	if(cnt == N) {
		dis += Math.abs(r-home[0]) + Math.abs(c-home[1]); // 집 까지의 거리 구하기
		min = Math.min(min, dis);
		return;
	}
	for(int i=0; i<N; i++) {
		if(v[i]) continue;
		v[i] = true;
			
		// 현재 위치와 순열에서 선택된 고객 집의 위치와의 거리 구해서 지금까지 거리에 더하기
		int newDis = dis + Math.abs(r-customer[i][0]) + Math.abs(c-customer[i][1]);
		perm(cnt+1, customer[i][0], customer[i][1], newDis);
		v[i] = false;
	}
}

 

전체 코드

package ps_02222;

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

public class Solution_d5_1247_최적경로 {
	static int N;
	static boolean[] v;
	
	static int[] company, home;
	static int[][] customer;
	static int min;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			N = Integer.parseInt(br.readLine());
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			company = new int[]{r, c};
			
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			home = new int[]{r, c};
			
			customer = new int[N][2];
			for(int i=0; i<N; i++) {
				r = Integer.parseInt(st.nextToken());
				c = Integer.parseInt(st.nextToken());
				
				customer[i][0] = r;
				customer[i][1] = c;
			}
			
			min = Integer.MAX_VALUE;
			v = new boolean[N];
			
			perm(0, company[0], company[1], 0);
			sb.append("#").append(t).append(" ").append(min).append("\\n");
		}
		System.out.println(sb.toString());
		br.close();
	}
	
	static void perm(int cnt, int r, int c, int dis) {
		if(dis > min) return;
		if(cnt == N) {
			dis += Math.abs(r-home[0]) + Math.abs(c-home[1]);
			min = Math.min(min, dis);
			return;
		}
		for(int i=0; i<N; i++) {
			if(v[i]) continue;
			v[i] = true;
			int newDis = dis + Math.abs(r-customer[i][0]) + Math.abs(c-customer[i][1]);
			perm(cnt+1, customer[i][0], customer[i][1], newDis);
			v[i] = false;
		}
	}
}

 

정리

순열을 모두 구한 후 거리 계산하는 것과 화려한 파라미터로 계산하는 건 거의 속도가 10배 차이..!!!

화려한 파라미터에 익숙해지자ㅏ!!