프로그래머스 - DFS 여행경로

JungWooLee·2022년 9월 22일
0

알고리즘

목록 보기
7/8
post-thumbnail

문제


문제접근

문제 풀이 전 해당 문제의 특이점을 몇가지 짚고 갑니다
1. 항상 "ICN" 공항에서 출발합니다
2. 한번 이동한 경로는 다시 이동하지 않습니다
3. 양방향이 아닌 왼쪽에서 오른쪽으로 향하는 단방향입니다
4. 모든 경로를 이용하여야 합니다
5. 가능한 경로중 알파벳 순서로 가장 앞의 경로를 반환합니다

처음에는 HashMap 을 통하여 모든 위치 정보는 boolean 타입으로 받아와 visited 처리하였다
다만 이때에 쓸때없는 메모리 낭비가 심하며 애초에 모든 위치 정보가 아니라 경로의 방문여부를 확인하여야 했다.. 😂문제를 잘읽자

또한 중요하게 봐야할점이 만약 List 타입으로 유망한 경로를 저장하였다고 하였을 때 각 경로또한 List 로 담는 방식을 채택하였는데 이것또한 Comparator 를 직접 지정해주어야 하며 원하는 결과값을 얻을 수 없었다

보통 이렇게 유망한 경우를 찾는 경우 DFS 를 활용한 백트래킹 알고리즘이 정석적으로 쓰이게 되는데 보통은 visited를 기준으로 true, false 설정하여 해당 분기점을 기준으로 뒤로 백트래킹이 된다


문제 풀이

DFS

public void dfs(String start, int cnt, String route, String[][] tickets){
        if(cnt == tickets.length){
            allPos.add(route);
            // 만약 모든 경로를 이동하였다면
            return;
        }
        // 현재 위치에서 시작, 이어진 곳들을 방문한다
        for (int i = 0; i < tickets.length; i++) {
            if(!visited[i] && start.equals(tickets[i][0])){
                // 현재위치이면서, 방문한적없는 루트라면
                visited[i] = true; // 방문처리
                // 다음 행선지를 루트에 추가
                dfs(tickets[i][1], cnt+1, route+","+tickets[i][1], tickets);
                visited[i] = false; // 백트래킹
            }
        }
    }
  • 시작위치 start, 현재 방문한 루트 카운트, 현재 루트, 그리고 티켓들을 받아온다
  • cnt 를 기준으로 경로의 방문 횟수가 모든 경로의 수와 같다면 return 시킨다, 이때에 List 에 경로정보를 담아준다
  • 모든 경로를 탐색하며, 시작점과 이어져있으며 방문한적 없는 경로일 경우 재귀적으로 dfs 를 실시한다
  • 모든 유망한 경우를 파악하기 위해 백트래킹 한다

solution

public String[] solution(String[][] tickets) {
        String[] answer = {};
        allPos = new ArrayList<>();
        visited = new boolean[tickets.length];
        dfs("ICN", 0, "ICN", tickets);
        Collections.sort(allPos);
        answer = allPos.get(0).split(",");
        return answer;
    }
  • 시작점은 ICN 을 보장
  • sort를 이용하여 문자열끼리 비교한다
  • 정렬된 이후의 가장 첫번째 문자열을 "," 를 기준으로 배열로 만든다

전체코드

import java.util.*;

class Solution {
    boolean[] visited;
    ArrayList<String> allPos; 

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        allPos = new ArrayList<>();
        visited = new boolean[tickets.length];
        dfs("ICN", 0, "ICN", tickets);
        Collections.sort(allPos);
        answer = allPos.get(0).split(",");
        return answer;
    }
    
    public void dfs(String start, int cnt, String route, String[][] tickets){
        if(cnt == tickets.length){
            allPos.add(route);
            // 만약 모든 경로를 이동하였다면
            return;
        }
        // 현재 위치에서 시작, 이어진 곳들을 방문한다
        for (int i = 0; i < tickets.length; i++) {
            if(!visited[i] && start.equals(tickets[i][0])){
                // 현재위치이면서, 방문한적없는 루트라면
                visited[i] = true; // 방문처리
                // 다음 행선지를 루트에 추가
                dfs(tickets[i][1], cnt+1, route+","+tickets[i][1], tickets);
                visited[i] = false; // 백트래킹
            }
        }
    }
    
}

0개의 댓글