[알고리즘] 프로그래머스 여행경로 (java) -bfs, dfs-

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

코딩테스트 연습 - 여행경로

 

 

 

프로그래머스 LEVEL3의 여행경로 문제를 풀어봤습니다.ㅎㅎ

이전 문제와 마찬가지로 탐색문제인데요.

이전 문제가 BFS 여서 그랬는지 BFS로도 풀 수 있겠다 싶어 처음에 BFS 로 접근했습니다.

솔직히 풀면서 너무 더러워져서 DFS 가 낫겟다 싶었는데 이왕 시작한거 끝을 볼려고 계속 풀었습니다...;;

코드는 다음과 같았는데요. 

하지만 주어진 테스트케이스는 다 맞는데 제출시 1,4 테스트케이스가 틀렸습니다.

분명 모든 케이스 검사한 것 같은데 틀려서 고군분투했으나 원인을 찾지 못했습니다. ㅠㅠ

아시는분은 댓글 달아주시면 감사하겠습니다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        // solution.solution(new String[][]{{"ICN", "SFO"}, {"ICN", "ATL"}, {"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}});
        solution.solution(new String[][]{{"ICN", "BBB"}, {"ICN", "ATL"}, {"BBB", "ICN"}});
    }

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        ArrayList<String> list = new ArrayList<>();
        Queue<Flight> queue = new LinkedList<>();
        boolean[] isVisited;
        for (int i = 0; i < tickets.length; i++) { // ICN 시작점인 경우 탐색
            if (!tickets[i][0].equals("ICN")) {
                break;
            }
            queue.clear();
            isVisited = new boolean[10000];
            isVisited[i] = true;
            queue.offer(new Flight(tickets[i][0], tickets[i][1], 1, "ICN", isVisited));
            while (!queue.isEmpty()) {
                if (queue.peek().cnt == tickets.length) { //끝까지 갔으면 결과리스트에 추가
                    Flight flight = queue.poll();
                    String history = flight.hisory + "," + flight.dst;
                    list.add(history);
                    continue;
                }
                Flight flight = queue.poll();
                String currentDst = flight.dst; // 현재 공항 도착지
                for (int j = 0; j < tickets.length; j++) { //다음 공항 탐색
                    String nextStart = tickets[j][0]; //다음 공항 출발
                    String nextDst = tickets[j][1]; //다음 공항 도착지
                    if (!flight.isVisited[j] && currentDst.equals(nextStart)) {
                        boolean[] nextVisited = new boolean[10000];
                        nextVisited = flight.isVisited.clone();
                        nextVisited[j] = true;
                        queue.offer(new Flight(nextStart, nextDst, flight.cnt + 1, flight.hisory + "," + tickets[j][0], nextVisited));
                    }
                }
            }
        }
        //정렬
        Collections.sort(list);
        answer = list.get(0).split(",");
        return answer;
    }

    class Flight {
        String start;
        String dst;
        int cnt;
        String hisory;
        boolean[] isVisited;

        public Flight(String start, String dst, int cnt, String hisory, boolean[] isVisited) {
            this.start = start;
            this.dst = dst;
            this.cnt = cnt;
            this.hisory = hisory;
            this.isVisited = isVisited;
        }
    }
}

 

 

 

그래서 바로 같은 로직으로 DFS로 풀어서 통과할 수 있었습니다. ㅎㅎ

로직은 비슷한데 BFS는 왜 실패하는지 미스테리네요..

 

1. 첫 시작은 ICN 으로 시작한다. (조건)

2. Flight 라는 class 를 정의한다. 출발지, 도착지, 들린항공기록, 들른 공항 개수,  방문한 공항 변수를 갖고 있다.

3. 처음 ICN 으로 시작하는 Flight 를 초기화 해주고 dfs 재귀를 돌리도록 한다.

4. dfs() 로 재귀를 돌며 방문을 아직 안하고 끝말있기(?) 조건에 맞는 공항을 탐색하고 찾은 경우 방문 표시와 들른 공항 개수 + 1, 출발지 등을 업데이트한다.

5. 공항을 공항티켓 개수만큼 들린 경우 resultList 에 해당 공항 기록을 추가해준다. (공항기록은 여러개 답이 나올 경우 알파벳 순이 가장 높은걸 출력해야하므로 , 로 구분한 String 형태로 구현하였다.

6. 총 결과를 오름차순하여 답을 도출한다.

 

통과한 풀이는 다음과 같습니다. 

[Java]

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    int size = 0;
    String[][] tickets;
    ArrayList<String> resultList = new ArrayList<>();

    public String[] solution(String[][] tickets) {
        String[] answer = {};
        boolean[] isVisited;
        this.tickets = tickets;
        size = tickets.length;
        for (int i = 0; i < tickets.length; i++) {
            if (tickets[i][0].equals("ICN")) {
                isVisited = new boolean[tickets.length];
                String start = tickets[i][0];
                String end = tickets[i][1];
                String history = tickets[i][0];
                isVisited[i] = true;
                Flight flight = new Flight(start, end, history, 1, isVisited);
                dfs(flight);
            }
        }
        //정렬
        Collections.sort(resultList);
        answer = resultList.get(0).split(",");
        return answer;
    }

    void dfs(Flight flight) {
        for (int i = 0; i < size; i++) {
            if (flight.cnt == size) {
                String history = flight.history + "," + flight.end;
                resultList.add(history);
                continue;
            }
            boolean[] isVisited = flight.isVisited.clone();
            String currentEnd = flight.end;
            String nextStart = tickets[i][0];
            if (!isVisited[i] && currentEnd.equals(nextStart)) {
                String history = flight.history + "," + nextStart;
                isVisited[i] = true;
                dfs(new Flight(tickets[i][0], tickets[i][1], history, flight.cnt + 1, isVisited));
            }
        }
    }

    class Flight {
        String start; //출발지
        String end; //도착지
        String history; //기록
        int cnt; // 공항 이동 총 횟수
        boolean[] isVisited; // 공항 방문 여부

        public Flight(String start, String end, String history, int cnt, boolean[] isVisited) {
            this.start = start;
            this.end = end;
            this.history = history;
            this.cnt = cnt;
            this.isVisited = isVisited;
        }
    }
}

 

[Kotlin]

import java.util.*

class Solution {
    var size = 0
    private lateinit var tickets: Array<Array<String>>
    var resultList = ArrayList<String>()

    fun solution(tickets: Array<Array<String>>): Array<String> {
        var answer = arrayOf<String>()
        var isVisited: BooleanArray
        this.tickets = tickets
        size = tickets.size
        for (i in tickets.indices) {
            if (tickets[i][0] == "ICN") {
                isVisited = BooleanArray(tickets.size)
                val start = tickets[i][0]
                val end = tickets[i][1]
                val history = tickets[i][0]
                isVisited[i] = true
                val flight = Flight(start, end, history, 1, isVisited)
                dfs(flight)
            }
        }
        //정렬
        resultList.sort()
        answer = resultList[0].split(",".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray()
        return answer
    }

    private fun dfs(flight: Flight) {
        for (i in 0 until size) {
            if (flight.cnt == size) {
                val history = flight.history + "," + flight.end
                resultList.add(history)
                continue
            }
            val isVisited = flight.isVisited.clone()
            val currentEnd = flight.end
            val nextStart = tickets[i][0]
            if (!isVisited[i] && currentEnd == nextStart) {
                val history = flight.history + "," + nextStart
                isVisited[i] = true
                dfs(Flight(tickets[i][0], tickets[i][1], history, flight.cnt + 1, isVisited))
            }
        }
    }

    data class Flight(var start: String //출발지
                      , var end: String //도착지
                      , var history: String //기록
                      , var cnt: Int // 공항 이동 총 횟수
                      , var isVisited: BooleanArray // 공항 방문 여부
    )
}

 

 

(추가로 다른분들 풀이를 보니 모두 DFS로 푸셨더라고요. )

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C%20-bfs%2Cdfs-

mtjin/algorithm_practice

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다!!