Iyoungman Back-end Developer

Programmers. 여행경로

2020-05-16
Algorithm
   

Problem

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


Think

  • 처음에는 경로를 찾을 때 단순 Map만 이용했고 주어진 예시도 맞았다.
  • 하지만 코드 제출을 했을 때 TC 1,2 번이 틀렸고
    반례가 떠오르지 않아 질문을 찾아봤다.

  • 반례는 아래와 같다.
[[ICN, COO], [ICN, BOO], [COO, ICN], [BOO, DOO]]

답은 ICN -> COO -> ICN -> BOO -> DOO 이다.

Map 혹은 Queue로 풀면 문제 조건에 따라 ICN -> BOO -> DOO 로 가서 경로가 없다.


  • 즉, 문제 조건에 직접적인 언급은 없지만 중간에 되돌아가야하는 경우가 생긴다.
  • 반례를 바탕으로 백트래킹으로 바꿔 해결했다.


Solved Code

import java.util.*;

class Solution {
   
    private static String[] result;
    private static boolean isEnd;

    public String[] solution(String[][] tickets) {
        result = new String[tickets.length + 1];

        //(1)
        Map<String, List<String>> ticketsMap = new HashMap<>();
        for (String[] ticket : tickets) {
            List<String> values = ticketsMap.getOrDefault(ticket[0], new ArrayList<String>());
            values.add(ticket[1]);
            ticketsMap.put(ticket[0], values);
        }

        //(2)
        Set<String> keys = ticketsMap.keySet();
        for (String key : keys) {
            List<String> values = ticketsMap.get(key);
            Collections.sort(values);

            ticketsMap.put(key, values);
        }

        //(3)
        dfs("ICN", 0, ticketsMap);

        return result;
    }

    private static void dfs(String current, int index, Map<String, List<String>> ticketMap) {
        result[index] = current;

        if (index == result.length - 1) {
            isEnd = true;
            return;
        }
        
        if (!ticketMap.containsKey(current)) {//갈곳이 없으면
            return;
        }

        List<String> nexts = ticketMap.get(current);
        for (int i = 0; i < nexts.size(); i++) {
            String next = nexts.get(i);

            if (!next.equals("") && !isEnd) {
                nexts.set(i, "");
                ticketMap.put(current, nexts);

                dfs(next, index + 1, ticketMap);

                nexts.set(i, next);
                ticketMap.put(current, nexts);
            }
        }
    }
    
}


Solved Process

1) 어떠한 공항에서 다른 공항들로 경로를 Map으로 담는다.

2) 문제 조건에 따라 공항을 정렬한다.

3) 백트래킹으로 이용해 결과를 구한다.

Comments

Content