[프로그래머스] 여행경로 Java, Golang 풀이 (DFS)

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

풀이

이 문제는 재귀를 사용한 DFS로 풀이할 수 있었다.

먼저 visited 배열을 생성해 재방문을 방지했다.

count를 사용해 모든 티켓을 사용했는지 확인하는 용도로 사용했다.

만약 모든 티켓을 사용했다면 results 에 값을 넣고 알파벳 순서대로 정렬한다.

자바 풀이(Golang은 아래에 있다)

import java.util.*;

class Solution {
    
    List<String> results;
    boolean[] visited;
    
    public String[] solution(String[][] tickets) {
        initialize(tickets.length);
        
        int cnt = 0;
        DFS(tickets, "ICN", "ICN", cnt);
        Collections.sort(results);
        
        return results.get(0).split(",");
    }
    
    private void initialize(int ticketCount) {
        this.results = new ArrayList<>();
        this.visited = new boolean[ticketCount];
    }
    
    private void DFS(String[][] tickets, String current, String result, int count) {
        //탈출조건
        if (count == tickets.length) {
            results.add(result);
            return;
        }
        
        //방문
        for (int i = 0; i < tickets.length; i++) {
            if (!visited[i] && tickets[i][0].equals(current)) {
                visited[i] = true;
                DFS(tickets, tickets[i][1], result+","+tickets[i][1], count+1);
                visited[i] = false;
            }
        }
    }
}

Golang 풀이

import (
    "strings"
    "sort"
)

const start = "ICN"
var results []string
var visited []bool

func solution(tickets [][]string) []string {
    initializer(len(tickets))
    dfs(tickets, start, start, 0)
    sort.Strings(results)
    return strings.Split(results[0], ",")
}

func initializer(count int) {
    visited = make([]bool, count)
}

func dfs(tickets [][]string, current, result string, count int) {
    //티켓 전부 사용하면 탈출
    if count == len(tickets) {
        results = append(results, result)
        return
    }
    for i := range tickets {
        //현재 위치에서 사용 가능한 티켓의 경우
        if !visited[i] && tickets[i][0] == current {
            visited[i] = true
            dfs(tickets, tickets[i][1], result+","+tickets[i][1], count+1)
            visited[i] = false
        }
    }
}

마치며

생각보다 간단한 문제였지만 문제를 이해하고 코드를 작성하는데까지 생각보다 많은 시간이 소요됐다.

문제를 천천히 읽고 이해하도록 노력이 필요하다..!

상기 문제는 프로그래머스 문제를 직접 풀고 해설한 내용입니다.
틀린 문제나 더 개선이 필요한 사항이 있다면 댓글로 공유해주세요!