[ 프로그래머스 JAVA ] 여행경로 | 배열 참조

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

 

1. ICN 이라는 문자열로 시작하는 티켓이면 DFS를 돌린다. 

2. ICN으로 시작해서 tickets.length+1 크기만큼 배열을 채우는 경로는 List에 담는다.

3. list를 정렬한다. (사전순으로 먼저 오는 것을 출력하기 위해)

4. list.get(0)의 배열을 출력한다. 

 

 

Collection 정렬

Collections.sort(list, (a,b)-> {
            for(int i=0; i<a.length; i++){
                int compare = a[i].compareTo(b[i]);
                if(compare!=0) // 동일한 문자열이 아니라면 
                    return compare; // 순서 변경 o
            }
            return 0; // 순서 변경 x 
        });
        
// compareTo : 문자열 비교 메서드

 

참조 배열

DFS 돌릴때 road배열을 clone 해서 list에 담게 된다. 

clone()을 사용해야 하는 이유는 Java에서 배열은 참조 타입이기 때문.

DFS를 사용할 때 같은 배열(road)을 재귀 호출에서 계속 사용하게 되면, 배열이 같은 메모리 공간을 참조하고 있기 때문에 그 값이 재귀 과정에서 덮어씌워진다. 따라서 매번 새로운 경로가 완성될 때마다 그 상태를 복사해서 저장해야 한다.

 

참조 배열 예시 

String[] road = new String[3];
road[0] = "A";
road[1] = "B";

list.add(road);  // 첫 번째 상태에서 추가
road[2] = "C";   // 나중에 값이 변경됨
list.add(road);  // 두 번째 상태에서 추가

//결과 
list[0]: ["A", "B", "C"]
list[1]: ["A", "B", "C"]

 

String[] road = new String[3];
road[0] = "A";
road[1] = "B";

list.add(road.clone());  // 첫 번째 상태에서 배열 복사 후 추가
road[2] = "C";           // 나중에 값이 변경됨
list.add(road.clone());  // 두 번째 상태에서 배열 복사 후 추가

// 결과
list[0]: ["A", "B", null]
list[1]: ["A", "B", "C"]

 

참조 타입 배열 vs 기본 타입 배열 

[기본 타입 배열]

배열 안에 int, char, double 같은 값 자체가 저장

.clone()을 사용하면 새로운 배열이 만들어지고, 값도 복사. 값은 완전히 독립적.

기본 타입 배열은 .clone()을 사용하면 깊은 복사가 이루어진다.

배열의 값 자체가 복사되기 때문에, 원본 배열과 복사된 배열은 서로 독립적.

 

[참조 타입 배열]

배열 안에 객체의 주소(참조값)가 저장.

.clone()을 사용하면 배열 자체는 복사되지만, 배열 안의 객체는 같은 것을 가리킨다. 객체는 공유됨.

참조 타입 배열 은 .clone()을 사용하면 얕은 복사가 이루어진다.

즉, 배열은 복사되지만 배열 내부에서 가리키는 객체의 참조값(주소)만 복사.

배열은 새롭게 생성되지만, 그 안의 객체는 원본 배열과 공유.

 

그런데 담기는 값에 상관없이 배열은 참조 타입이기 때문에 

int[] 배열이었어도, .clone()을 해주었어야 한다. 

 

따라서 아래와 같이 road배열을 clone() 해주어야 한다. 

 if(cnt == tickets.length){
            road[tickets.length] = tickets[idx][1];
            list.add(road.clone());
            visit[idx] = false;
            return;
        }

 

Solution

import java.util.*;

class Solution {
    boolean[] visit;
    String[][] tickets;
    String[] answer;
    List<String[]> list;
    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        
        // Arrays.sort(tickets, (a,b)-> a[1].compareTo(b[1]));
        list = new ArrayList<>();
        
        for(int i=0; i<tickets.length; i++){
            if(tickets[i][0].equals("ICN")){
                visit = new boolean[tickets.length];
                String[] road = new String[tickets.length+1];
                road[0] = "ICN";
                DFS(i,1, visit, road);
            }
        }
        
        Collections.sort(list, (a,b)-> {
            for(int i=0; i<a.length; i++){
                int compare = a[i].compareTo(b[i]);
                if(compare!=0)
                    return compare;
            }
            return 0;
        });
        
        return list.get(0);
    }
    public void DFS(int idx, int cnt, boolean[] visit, String[] road){
        visit[idx] = true;
        
        if(cnt == tickets.length){
            road[tickets.length] = tickets[idx][1];
            list.add(road.clone());
            visit[idx] = false;
            return;
        }
        
        String find = tickets[idx][1];
        
        for(int i=0; i<tickets.length; i++){
            if(!visit[i]&& tickets[i][0].equals(find)){
                road[cnt] = find;
                DFS(i, cnt+1,visit, road);
            }
        }
        visit[idx] = false;
    }
}