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

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

프로그래머스

 

해당 문제는 DFS를 활용하여 풀 수 있었다.

처음에는 HashMap을 사용하여 풀려고 하였다.

HashMap <String, List <String>>의 맵을 만들고, 키 값에 시작점을 넣고 value값은 도착점을 넣으려고 하였다.

(키값이 중복이 있을 수 있기 때문에 value의 값을 List <String>으로 하려 함)

하지만 이러한 풀이는 value의 순서에 따라 전부 방문하지 못하는 경우가 생기기도 하였다.

 

따라서 전부다 탐색을 시도해야 한다고 판단하고 DFS를 활용해보았다.

 

핵심

DFS메서드에 매개변수로 경로를 String을 통해 담았다.

이를 통해 더 쉽게 값들을 저장할 수 있었다.

 

정답 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    List<String> results;
    boolean[] visited;
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        results = new ArrayList<>();
        int count = 0;
        DFS(count,"ICN","ICN",tickets);
        Collections.sort(results);
        return results.get(0).split(" ");
    }
    void DFS(int count , String present, String result , String[][] tickets){
        if (count == tickets.length){
            results.add(result);
            return;
        }
        for (int i = 0; i<tickets.length; i++){
            if (!visited[i] && tickets[i][0] == present){
                visited[i] = true;
                DFS(count+1, tickets[i][1],result+" "+tickets[i][1] ,tickets);
                visited[i] =false;
            }
        }
    }
}

해설

재방문을 하지 못하게 visited배열을 만들어준다.

results를 만든 이유는 정답이 여러 개가 나올 수 있기 때문이다.

DFS의 매개변수를 보면 카운트, 현재 위치, 경로, 티켓이 있다.

카운트는 말 그대로 모든 경로를 갔는지 체크하는 용도로 사용된다.

현재 위치는 티켓의 시작점을 찾는 용도로 사용된다.

경로는 여태까지 들린 경로를 저장하였다. -> 모든 곳을 방문했다면 results에 add 한다.

 

 

배운 점

처음에 경로를 어떻게 저장할지 고민을 하다가, 매개변수를 통해 누적시키는 방법을 사용하였다.

이러한 방법을 사용하니 코드가 깔끔해지고 이해하기 편해졌다고 생각한다.

처음에 맵을 사용하려 한 부분이 예외를 제대로 생각하지 못하고 시도하였다.

만약 처음부터 제대로 에지 케이스나 코너 케이스에 대해 조금 더 생각하고 풀었다면,

더 쉽게 풀었을 것이라는 생각을 하였다.

문제를 풀 때 빠르게 푸는 데에 집중하는 경향이 있는데, 조금 더 분석하고 차분하게 풀어야겠다.