[Programmers:DFS/BFS] 여행경로

❓문제

주어진 항공권을 모두 이용한 여행 경로(여러 개일 경우 알파벳 순으로)

 

---

🖐️손코딩

Tickets을 인덱스 기준으로 사전순으로 정렬 => 항상 사전순임을 보장

bfs(curNode){
	for(i: 0 ~ tickets 수)
    	if(visited[i] == false)
        	if(curNode[1] == Tickets[i][0])
            	answer.add(Tickets[i])
                curNode = Tickets[i]
                bfs(curNode)
                answerlist.remove
                visited[i] = false
            
}

main{
	tickets을 오름차순으로 정렬
    
    for(i: 0 ~ tickets 수)
    	if(ICN에서 출발하는 티켓)
        	visited[i] = true
            bfs(tickets[i])
            answerlist.remove
            visited[i] = false
            
}

 

---

👩‍💻구현 코드

import java.util.*;

class Solution {
    boolean[] visited;
    String[][] inputs;
    ArrayList<String[]> answerlist;
    
    private boolean dfs(String[] curNode){
        if(answerlist.size() == inputs.length){
            return true; // 모든 티켓을 사용
        }
        
        for(int i = 0; i<inputs.length; i++){
            if(!visited[i]){
                if(curNode[1].equals(inputs[i][0])){
                    visited[i] = true;
                    answerlist.add(inputs[i]);
                    
                    if(dfs(inputs[i])){
                        return true;
                    }
                    
                    answerlist.remove(answerlist.size()-1);
                    visited[i] = false;
                }
            }
            
        }
        
        return false;
    }
    
    public String[] solution(String[][] tickets) {
        visited = new boolean[tickets.length];
        answerlist = new ArrayList<>();
        
        Arrays.sort(tickets,(a,b) -> {
            if(a[0].equals(b[0])){
                return a[1].compareTo(b[1]);
            }
            
            return a[0].compareTo(b[0]);
        });
        
        inputs = tickets;
        
        for(int i = 0; i<inputs.length; i++){
            if(inputs[i][0].equals("ICN")){
                visited[i] = true;
                answerlist.add(inputs[i]);
                
                if(dfs(inputs[i])){
                    break;
                }

                answerlist.remove(answerlist.size()-1);
                visited[i] = false;
            }
        }
        
        
        String[] answer = new String[answerlist.size()+1];
        
        answer[0] = answerlist.get(0)[0];
        
        for(int i = 0; i<answerlist.size(); i++){
            answer[i+1] = answerlist.get(i)[1];
        }
        
        
        return answer;
    }
}

 

1. BFS를 boolean으로 리턴하는 이유: 정답을 찾으면 즉시 탐색을 끝내기 위해

//void 였다면

ICN
├── A
│   └── ...
└── B
    └── 정답
    
정답을 찾았더라도 DFS(A) DFS(B) 처럼 모든 경우를 끝까지 탐색하게 됨!!

 

2. 테스트1 런타임 에러가 뜬 이유: 

curNode = inputs[i] 로 재귀 함수 안의 기준점인 curNode를 바꿔버려서 백트래킹을 하게 되면 엉뚱한 값을 기준으로 비교하게 됨 => DFS가 무한 루프에 빠져 스택 오버플로우 에러가 발생!!

---

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

프로그래머스