코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS) > 여행경로

이전 코드

import java.util.*;


class Solution {
    ArrayList <Ticket> ticketsArrayList = new ArrayList<>();
    ArrayList <String> ansArrayList = new ArrayList<>();
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        
        for (String [] ticket : tickets){
            ticketsArrayList.add(new Ticket(ticket[0], ticket[1]));
        }
        
        dfs(ticketsArrayList, "ICN", "ICN");
        Collections.sort(ansArrayList);

        return ansArrayList.get(0).split(",");
    }
    
    public void dfs (ArrayList <Ticket> ticketArrayList, String route, String airport){
        ArrayList <Ticket> usableticketArrayList = new ArrayList<>();
        if (ticketArrayList.size() == 0){
            ansArrayList.add(route);
            return;
        }
        
        for (Ticket ticket : ticketArrayList){
            if (ticket.getDeparture().equals(airport)){
                usableticketArrayList.add(ticket);
            }
        }
        
        if(usableticketArrayList.size() == 0){
            return;
        }
        
        for (Ticket ticket : usableticketArrayList){
            ArrayList <Ticket> tickets = new ArrayList<>(ticketArrayList);
            tickets.remove(ticket);
            dfs(new ArrayList<>(tickets), route + "," + ticket.getArrival(), ticket.getArrival());
        }
        
    }
    
    class Ticket implements Comparable<Ticket> {
        String departure;
        String arrival;
        
        public Ticket (String departure, String arrival){
            this.departure = departure;
            this.arrival = arrival;
        }
        public String getArrival(){
            return arrival;
        }
        public String getDeparture(){
            return departure;
        }
        
        @Override
        public int compareTo(Ticket ticket) {
            return this.getArrival().compareTo(ticket.getArrival());
        }
    }
}

최근 코드

import java.util.*;

class Solution {
    ArrayList<String> ansArrayList;
    public String[] solution(String[][] tickets) {
        ArrayList <Ticket> ticketArrayList = new ArrayList<>();
        ansArrayList = new ArrayList<>();
        for (String [] ticket : tickets){
            ticketArrayList.add(new Ticket (ticket[0], ticket[1]));
        }
        getRoot(ticketArrayList, "ICN", "ICN");
        Collections.sort(ansArrayList);
        
        return ansArrayList.get(0).split(",");
    }
    
    public void getRoot(ArrayList <Ticket> arrayList, String root, String current){
        
        if (arrayList.size() == 0){
            ansArrayList.add(root);
            return;
        }
        ArrayList<Ticket> usableArrayList = new ArrayList<>();
        for (Ticket ticket : arrayList){
            if (ticket.getDeparture().equals(current)){
                usableArrayList.add(ticket);
            }
        }
        if (usableArrayList.size() == 0){
            return;
        }
        
        for (Ticket ticket : usableArrayList){
            ArrayList <Ticket> ticketArrayList = new ArrayList<>();
            ticketArrayList.addAll(arrayList);
            ticketArrayList.remove(ticket);
            getRoot(ticketArrayList, root + "," + ticket.getArrival(), ticket.getArrival());
        }
    }
}

class Ticket implements Comparable<Ticket> {
        String departure;
        String arrival;
        
        public Ticket (String departure, String arrival){
            this.departure = departure;
            this.arrival = arrival;
        }
        public String getArrival(){
            return arrival;
        }
        public String getDeparture(){
            return departure;
        }
        
        @Override
        public int compareTo(Ticket ticket) {
            return this.getArrival().compareTo(ticket.getArrival());
        }
    }