[SWEA] 최적경로 JAVA

오늘 재밌는 문제?를 풀어서 리뷰해본다.
알고리즘을 풀때 사소한 코드 하나 하나 질문할 멘토가 있다는 건 정말 좋은 점인거 같다.
싸피 최고 싸피 짱 삼전 짱

문제 링크

문제 빌드업

1. 처음 문제를 읽을 때는 두점 사이의 거리와 한점에서 모든 지점을 가는 줄 알고 다익스트라, bfs/dfs를 생각했다
2. 가장 짧은 경로의 이동거리만 알면 된다. 경로 자체를 찾는것이 아님
3. N<=10이므로 N!도 가능 => 완탐
4. 순열을 구한 후 거리 구하기로 풀어야겠다

시행착오

1. 문제를 대충 읽고 회사 - 고객 - 회사 - 집 인줄 알았다 ㅎ

첫 코드

import java.util.*;
class Solution
{
    static Pos[] cus;
	static Pos company;
	static Pos home;
	static boolean[]visited;
	static int []order;
	static int[][]distance;//company는 n번째
	static int n;
	static int answer;
	public static void main(String args[]) throws Exception
	{
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for (int t = 1; t <= T; t++) {
			n=sc.nextInt();
			cus=new Pos[n];
			visited=new boolean[n];
			order=new int[n];
			distance=new int[n+2][n+2];
			answer=Integer.MAX_VALUE;
			int a=sc.nextInt();
			int b=sc.nextInt();
			company=new Pos(a,b);
			a=sc.nextInt();
			b=sc.nextInt();
			home=new Pos(a,b);
			for (int i = 0; i < n; i++) {
				int c=sc.nextInt();
				int d=sc.nextInt();
				cus[i]=new Pos(c,d);
			}
			permute(0);
			System.out.println("#"+t+" "+answer);
		}

	}
	static void permute(int count) {
		if(count==n) {
			//다 구함
			answer=Math.min(answer,getAnswer());
			return;
		}
		for (int i = 0; i < cus.length; i++) {
			if(visited[i])continue;
			//가거나
			visited[i]=true;
			order[count]=i;
			permute(count+1);
			visited[i]=false;
			//안가거나
		}
	}
	static int getAnswer() {
		//order 순회하면서 길이 합 구하기
		//회사- 첫 고객, 마지막 고객-집도 더해야함
		int sum=0;
		sum+=getDistance(company,cus[order[0]],n,order[0]);
		for (int i = 0; i < n-1; i++) {
			if(distance[order[i]][order[i+1]]!=0) {
				sum+=distance[order[i]][order[i+1]];
			}
			else sum+=getDistance(cus[order[i]],cus[order[i+1]],order[i],order[i+1]);
		}
		sum+=getDistance(home,cus[order[n-1]],n+1,order[n-1]);
		return sum;
	}
    // 두 점의 거리를 구하는 메소드
    //distance배열을 만들어 거리를 저장해줬다.
	static int getDistance(Pos a,Pos b,int i1,int i2) {
		int d=Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
		distance[i1][i2]=d;
		distance[i2][i1]=d;
		return d;
	}
	static class Pos{
		int x;
		int y;
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

처음에는 순열을 다 구하고 마지막에 거리를 계산해줬다.
불필요한 배열도 많고 변수도 많아서 리팩토링이 필요해 보였다.

두번째 코드

두번째에서는 getAnswer()의 for문에 if(distance[order[i]][order[i+1]]!=0)을 넣어 합을 구하면서 sum이 answer보다 크면 굳이 뒤를 다 더하지 않게 조건문을 넣어주었다.

나는 이 코드를 넣으면 시간이 더 줄 수 있다고 생각했다..!
하지만,,

늘었다!!!
조금이라 사실 문제 정답 여부와는 상관이 없겠지만, 궁금증이 생겼다.

이후 멘토님께 여쭤보니 for문으로 합을 구하는 건 O(1*n)이지만 조건문에서 조건을 확인하는건 O(1000)은 잡아야한다고 하셨다.
나는 무조건 for문을 빠져나오는게 좋을 거라 생각했는데, n값이 작고 가지치기 할 경우가 없다면 굳이 반복문을 빠져나오게 항상 시간적 이득을 얻는건 아니었다.

세번째 풀이

그렇다면 어떨 때 조건문을 써서 빠져나올 것인가?
위에 적은대로 가지치기를 해서 뒤에 경우를 크게 줄일 경우이다.
그래서 sum을 순열을 구한 후 계산하지 않고, 순열을 구하면서 더해주었다.

import java.util.*;

public class Solution {
	static Pos[] location;
	static boolean[]visited;
	static int prev;//cus index
	static int[][]distance;//company는 n번째, home n+1
	static int n;
	static int answer;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for (int t = 1; t <= T; t++) {
			n=sc.nextInt();
			location=new Pos[n+2];
			visited=new boolean[n];
			distance=new int[n+2][n+2];
			answer=Integer.MAX_VALUE;
			int a=sc.nextInt();
			int b=sc.nextInt();
			location[n]=new Pos(a,b);
			prev=n;
			a=sc.nextInt();
			b=sc.nextInt();
			location[n+1]=new Pos(a,b);
			for (int i = 0; i < n; i++) {
				a=sc.nextInt();
				b=sc.nextInt();
				location[i]=new Pos(a,b);
			}
			
			permute(0,0);
			
			System.out.println("#"+t+" "+answer);
		}

	}
	static void permute(int count,int sum) {
		if(count==n) {
			//다 구함
			//System.out.println(Arrays.toString(order));
			//마지막 고객- 집
			sum+=getDistance(n+1, prev);
			answer=Math.min(answer,sum);
			return;
		}
		if(sum>=answer)return;
		for (int i = 0; i < n; i++) {
			if(visited[i])continue;
			//가거나
			visited[i]=true;
			int d=0;
			int temp=prev;
			if(distance[prev][i]!=0) {
				d=distance[prev][i];
			}else d=getDistance(prev,i);
			prev=i;
			permute(count+1,sum+d);
			prev=temp;
			visited[i]=false;
			//안가거나
		}
	}
	static int getDistance(int i1,int i2) {
		Pos a=location[i1];
		Pos b=location[i2];
		int d=Math.abs(a.x-b.x)+Math.abs(a.y-b.y);
		distance[i1][i2]=d;
		distance[i2][i1]=d;
		return d;
	}
	static class Pos{
		int x;
		int y;
		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

엄청 줄었다!!!! 대~박

맞은 문제지만 코드 한줄 한줄 고민하고 리팩토링해보니 너무 재밌었다.
물론 마지막 코드에서도 리팩토링할 부분은 많다.
입출력 방식이라던지, 변수 전역화 부분 이라던지...
그래도 유의미한 고민을 한거 같아서 만족하고 더욱 고민하고 코드를 음미할 수 있는 개발자가 되기 위해 공부해야겠다