Programmers : 여행경로

풀이요약

Map 을 활용한 그래프

풀이 상세

1. 문자열을 기반으로 다음 장소로 갈 수 있는 그래프 형태를 구현하다 보니 Map 을 선택하게 되었다.

2. DFS 를 통해 장소를 이동한다. 단 동일한 좌표에 대한 제한사항이 없으므로 방문처리가 필요하다. 나의 경우 다음 좌표의 이름을 먼저 저장한 후, 해당 좌표를 X 로 변경하는 식으로 방문처리를 진행하였다.

3. 답안이 여러개인 경우가 존재한다. 이 경우 알파벳 순서가 앞서는 것을 반환을 해주어야 하는데, 특별한 정렬식이 기억나지 않아 문자열마다 char 로 반환하여 크기를 비교했다.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    static Map<String, List<String>> psv = new HashMap<>();
    static List<String> ans;

    private static void input(String[][] tickets) {
        for (int i = 0; i < tickets.length; i++) {
            List<String> currList = psv.get(tickets[i][0]);
            if (currList != null) {
                psv.get(tickets[i][0]).add(tickets[i][1]);
            } else {
                psv.put(tickets[i][0], new ArrayList<>());
                psv.get(tickets[i][0]).add(tickets[i][1]);
            }
        }
    }

    private static void updateAns(List<String> currList) {
        ans = new ArrayList<>();
        for (int i = 0; i < currList.size(); i++) ans.add(new String(currList.get(i)));
    }

    private static void check(List<String> currList) {
        outer:
        for (int i = 1; i < currList.size(); i++) {
            char[] ansStr = ans.get(i).toCharArray();
            char[] currStr = currList.get(i).toCharArray();
            for (int j = 0; j < 3; j++) {
                if (ansStr[j] != currStr[j]) {
                    if (currStr[j] < ansStr[j]) updateAns(currList);
                    break outer;
                }

            }
        }
    }

    private static void solve(int N, String name, List<String> currList) {
        if (currList.size() >= N + 1) {
            if (ans != null) check(currList);
            else updateAns(currList);
            return;
        }
        List<String> nextTickets = psv.get(name);

        if(nextTickets != null) {
            for (int i = 0; i < nextTickets.size(); i++) {
                String next = new String(nextTickets.get(i));
                if (next.length() <= 1) continue;
                nextTickets.set(i, "X");
                currList.add(next);
                solve(N, next, currList);
                currList.remove(currList.size() - 1);
                nextTickets.set(i, next);
            }
        }

    }

    private static String[] output(int N) {
        String[] temp = new String[N];
        for(int i=0; i<N; i++) {
            temp[i] = ans.get(i);
        }
        return temp;
    }

    public static String[] solution(String[][] tickets) {
        input(tickets);
        List<String> tmp = new ArrayList<>();
        tmp.add("ICN");
        solve(tickets.length, "ICN", tmp);
        return output(tickets.length+1);
    }
}