여행경로 자바

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

프로그래머스

 

여행경로 L3

첫 접근

for문을 수행해서 ICN인경우 dfs를 수행하고 방문처리를 한다.

dfs를 수행하면서 리스트에 값을 담고 다 순회했는지 확인한다.

다 순회했는지 확인하는건 visited를 for문 돌려서 참인 경우 2차원 리스트에 해당 리스트를 반환한다.

위 방법으로 하려고 했지만 구현에 실패했다.

-> 실패코드

public class 여행경로 {

    static List<List<String>> list = new LinkedList<>();
    static List<String> list2 = new LinkedList<>();
    static boolean[] visited;
    public static void main(String[] args) {
        String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
        System.out.println(solution(tickets));
    }

    public static String[] solution(String[][] tickets) {
        String[] answer = {};
        for (int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals("ICN")){
                visited = new boolean[tickets.length];
                dfs(i, tickets);
            }
        }
        return answer;
    }

    private static void dfs(int index, String[][] tickets) {
        for (int i = 0; i < tickets.length; i++) {
            if(visited[i] || !tickets[i][0].equals(tickets[index][1]))continue;
            visited[i]= true;
            list2.add(tickets[i][0]);
            dfs(index, tickets);
            visited[i] = false;
            //list2.remove(list2.size()-1);
        }
    }
}

문제점

1. 항상 for문을 두번 쓴다. for문으로 ICN인 경우 dfs안에서 for문으로 또 탐색하는데 그러지 말고 그냥 ICN을 보내고 for문으로 탐색을 수행한다. ⇒ 생각의 전환이 필요할듯? dfs안에 for문이 있으면 모든 경우를 다 돈다.
2. 2차원 리스트에 값을 담고 빼고 할 필요가 없다. string을 선언해서 공백을 주고 필요한 경우마다 붙여주면 필요할 때 split해서 사용가능
3. visited처리를 for문으로 돌리지 말고 count값으로 배열 길이랑 맞춰보자

package programmers.level3;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class 여행경로 {

    static List<String> list = new LinkedList<>();

    static boolean[] visited;
    public static void main(String[] args) {
        String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
        System.out.println(solution(tickets));
    }

    public static String[] solution(String[][] tickets) {
        String[] answer = {};
        visited = new boolean[tickets.length];
        dfs("ICN", "ICN", tickets, 0);
        Collections.sort(list);
        answer = list.get(0).split(" ");
        return answer;
    }

    private static void dfs(String start, String target, String[][] tickets, int count) {
        if(count == tickets.length) {
            list.add(target);
            return;
        }

        for (int i = 0; i < tickets.length; i++) {
            if(visited[i] || !start.equals(tickets[i][0])) continue;
            visited[i]= true;
            dfs(tickets[i][1], target + " " + tickets[i][1], tickets, count+1);
            visited[i] = false;
        }
    }
}