[java] 프로그래머스 - 여행경로

문제

프로그래머스-여행경로
ICN에서 시작하는 여행경로를 짜는 문제. 단, 모든 티켓을 사용해야하고 가능한 경로 중에서 알파벳 순서가 앞서는 경로를 return해야한다.

풀이

어려웠던 점, 기존에 풀던 index를 이용하는게 아닌 String을 가지고 다뤄야 했음..
또한 모든 티켓을 사용한다는 점을 처음엔 잊어버려서 알파벳 우선순위로 경로를 짜서 오답이 나옴.

• 소스코드(1) 나는 경로들을 stringbuilder를 사용해서 기록하면서 진행했는데 이때 알파벳 우선순위를 가지는 정답을 저장해야하므로 ZZZ를 min변수에 저장했다.
  또한 전체 티켓을 사용했는지 판단하기 위한 t 변수를 두었다.
• 소스코드 (2)
  티켓들을 돌면서 시작지역, 도착지역들을 hashmap에 등록해주었다.
  연결정보를 담을 conn에서 지역이름(string)으로 인덱스(integer)에 접근하기 위해 함수를 만들었고,
  시작지역의 인덱스에 도착지역들을 추가했다. 그리고 티켓 개수 증가
• 소스코드 (3)
  현재 차례의 지역에서 더이상 갈 곳이 없다면 종료를 하는데, 이때 티켓을 다 사용한게 아니라면 조건에 만족하지않으므로 종료한다.
  만일 min에 저장되어있는게 현재 기록보다 알파벳 우선순위가 있다면(compareTo의 값이 0보다 크다면)
  min을 갱신해주고 종료한다.
• 소스코드 (4)
  현재 지역에서 갈 수 있는 목적지를 다 가본다. 한 여행지로 보낸다음 돌아와서는 다음 목적지를 가볼 수 있게
  제외했던 값들을 넣어줘야한다. 현재 가지고있는 여행기록이 min보다 큰 경우는 종료처리했다.

소스코드

import java.util.HashMap;
import java.util.LinkedList;
class Solution {
HashMap<String, LinkedList<String>> conn = new HashMap<>();
// (1)
	String min = "ZZZ";
	int t=0;
	public String[] solution(String[][] tickets) {
		// 항상 ICN에서 출발함
		conn.clear();

		StringBuilder sb = new StringBuilder("ICN,");
		// (2)
		for (int i = 0; i < tickets.length; i++) {
			String from = tickets[i][0];
			String to = tickets[i][1];
			checkLoc(from, to);
			conn.get(from).add(to);
			t++;
		}
		dfs("ICN", sb);
		return min.split(",");
	}

	private void dfs(String curr, StringBuilder sb) {
		// (3)
		if (conn.get(curr).size() == 0) {
			if(t!=0)
				return;
			if (min.compareTo(sb.toString()) > 0) {
				min = sb.toString();
			}
			return;
		}
		// (4)
		if(min.compareTo(sb.toString())<0) {
			return;
		}
		for (int i = 0; i < conn.get(curr).size(); i++) {
			String nxt = conn.get(curr).removeFirst();
			StringBuilder sn = new StringBuilder(sb);
			sn.append(nxt).append(",");
			t--;
			dfs(nxt, sn);
			t++;
			conn.get(curr).add(nxt);
		}
	}

	private void checkLoc(String from, String to) {
		if (!conn.containsKey(from)) {
			conn.put(from, new LinkedList<>());
		}
		if (!conn.containsKey(to)) {
			conn.put(to, new LinkedList<>());
		}
	}
}

다른사람의 코드

import java.util.*;

class Solution {
    List<Stack<String>> result;
    String[][] tickets;

    public String[] solution(String[][] tickets) {
        result = new ArrayList<>();
        this.tickets = tickets;

        boolean[] visited = new boolean[tickets.length];
        Stack<String> st = new Stack<>();
        st.push("ICN");

        dfs(visited, st, 0);

        if (result.size() > 1) {
            Collections.sort(result, new Comparator<Stack<String>>() {
                @Override
                public int compare(Stack<String> o1, Stack<String> o2) {
                    for (int i = 0; i < o1.size(); i++) {
                        String s1 = o1.get(i);
                        String s2 = o2.get(i);

                        if (!s1.equals(s2)) {
                            return s1.compareTo(s2);
                        }
                    }

                    return 0;
                }
            });
        }

        Stack<String> res = result.remove(0);
        String[] answer = new String[res.size()];

        for (int i = 0; i < answer.length; i++) {
            answer[i] = res.get(i);
        }

        return answer;
    }

    public void dfs(boolean[] visited, Stack<String> st, int len) {
        if (len == tickets.length) {
            Stack<String> res = new Stack<>();
            for (String s : st) {
                res.push(s);
            }

            result.add(res);
            return;
        }

        String arrive = st.peek();

        for (int i = 0; i < tickets.length; i++) {
            String[] tic = tickets[i];

            if (!visited[i] && arrive.equals(tic[0])) {
                st.push(tic[1]);
                visited[i] = true;

                dfs(visited, st, len + 1);

                visited[i] = false;
                st.pop();
            }
        }
    }
}