오늘 재밌는 문제?를 풀어서 리뷰해본다.
알고리즘을 풀때 사소한 코드 하나 하나 질문할 멘토가 있다는 건 정말 좋은 점인거 같다.
싸피 최고 싸피 짱 삼전 짱
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;
}
}
}
엄청 줄었다!!!! 대~박
맞은 문제지만 코드 한줄 한줄 고민하고 리팩토링해보니 너무 재밌었다.
물론 마지막 코드에서도 리팩토링할 부분은 많다.
입출력 방식이라던지, 변수 전역화 부분 이라던지...
그래도 유의미한 고민을 한거 같아서 만족하고 더욱 고민하고 코드를 음미할 수 있는 개발자가 되기 위해 공부해야겠다