[JAVA]SWExpert_1247_최적경로

문제링크

https://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

 

 

 

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

public class Solution {

	static int T,N;
	static int office[],house[];
	private static int seq[];
	static ArrayList<Node> customer = new ArrayList<>();
	static int shortestDistance;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine()); //test case 
		
		for(int t=0;t<T;t++) {
			shortestDistance = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine()); //고객 수
			seq = new int[N];
			st = new StringTokenizer(br.readLine());
			office = new int[] {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())}; //기사 회사 좌표
			house = new int[] {Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())}; //기사 집 좌표
			for(int i=0;i<N;i++) {
				customer.add(new Node(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()))); //고객 집 좌표 
			}
			
			/*System.out.println("회사 :"+Arrays.toString(office));
			System.out.println("고객 집");
			for(int i=0;i<customer.size();i++)
				System.out.println(customer.get(i).x+" "+customer.get(i).y);
			System.out.println("기사 집 :"+Arrays.toString(house));*/
			perm(0,0);
			System.out.println("#"+(t+1)+" "+shortestDistance);
			customer.clear();
		}
		
		//dfs?

	}
	
	private static void dfs() {
		int len = 0;
		//회사랑 첫번째 고객 사이 거리
		len += (Math.abs(office[0] - customer.get(seq[0]).x) + Math.abs(office[1]-customer.get(seq[0]).y));
		for(int i=0,size = seq.length-1;i<size;i++) {
			len += (Math.abs(customer.get(seq[i]).x - customer.get(seq[i+1]).x) + Math.abs(customer.get(seq[i]).y - customer.get(seq[i+1]).y));
			if(len>shortestDistance) break;
		}
		len += (Math.abs(house[0] - customer.get(seq[seq.length-1]).x) + Math.abs(house[1]-customer.get(seq[seq.length-1]).y));
		shortestDistance = (shortestDistance>len)?len:shortestDistance;
		//System.out.println("최단 거리 :"+shortestDistance);
		return;
	}
	
	private static void perm(int cnt,int flag) {
		//비트 마스킹 이용해서 순열 구하기
		if(cnt == N) {
			/*System.out.println("현재 방문 순서");
			System.out.println(Arrays.toString(seq));*/
			dfs();
			return;
		}
		
		for(int idx=0;idx<N;idx++) {
			if((flag & 1<<idx )!=0) continue;
			seq[cnt] = idx;
			perm(cnt+1,flag|1<<idx);
		}
	}
	
	static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

 

뭔가 dfs로 풀고싶었는뎅 풀다보니까 그냥 순열로 풀었다

시간을 뭔가 더 줄이고싶었는뎅 잘 모르겠땅

 

중간에 계속 길이를 구하면서 만약 아직 끝까지 도달하지않았는데도 현재 최소길이보다 길다면 그냥 break문으로 빠져나와서 더 이상 계산하지 않도록 했다.

 

또한 순열은 비트마스킹을 이용하여서 풀었다.

현재 순열이 구해지면 dfs()함수로 들어가서 최소길이를 구하는 식으로 진행하였다.

 

 

---

고객의 좌표는 ArrayList<int[]>로 저장하다가 따로 배열로 빼서 저장하기가 귀찮아서 Node 클래스를 만들어서

ArrayList<Node>로 접근하였다.