[Unsolved][C++] 프로그래머스 여행경로

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

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

 

1. 서론

 

Level 3 답게 진짜 독한 문제다....(독한 건 이걸 못 푸는 나일지도^^)

처음에는 BFS네... 근데 어차피(?) 모든 곳을 방문해야 하니까 굳이 복잡하게 안 풀고 직관적으로 풀어야지

=> 시간초과 걸림(오래 걸려서가 아니라 방향을 못 찾아서 무한 돌아서)

그리고 반례 찾아보다가 한 번만 다음 도착지가 있는지 확인하면 되는 줄 알았는데 그 경로를 선택했어도 그다음에서 안될 수 있다는 사실을 깨달음, 즉 백트래킹 문제라는 사실을 깨달음

=> 코드 나름대로 백트래킹식으로 짜 봄 => 안 돌아감 => 인터넷에서 최대한 내가 생각했던 것과 비슷하게 푼 코드를 찾음...

 

 

2. 문제 풀이

 

항공권이 출발지와 도착지가 한 세트로 문자열 배열로 주어진다. 

이 경우에 모든 항공권을 사용해서 이동했을 때 이동경로를 문자열 배열로 저장하는 게 문제이다.

그리고 갈 수 있는 곳이 여러 곳인 경우 사전 순으로 이동한다.

방문할 수 없는 경우는 없고 의외로 문제에서 제일 중요한 키포인트는

 

tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.

 

이 부분이었다.... b로 가는 항공권이 여러 개라서 그중 사전 순으로 선택을 했는데 그 선택 때문에 방문할 수 없는 경우가 생긴다. 그래서 사전 순도 중요하지만 그보다 중요한 건 모든 항공권을 사용해서 도착할 수 있는 경우를 만드는 것이다.

 

이 부분 때문에 서론에서 말한 것처럼 반례도 많이 보고 허튼짓도 많이 하다가 코드를 짤 역량이 없음을 인정하고 코드를 찾아보게 되었다.

 

https://velog.io/@inryu/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-C-%EC%97%AC%ED%96%89%EA%B2%BD%EB%A1%9C

[프로그래머스 / C++] 여행경로

 

수많은 블로그와 코드들을 보았는데 가장 내가 생각했던 방향과 비슷하고 이해하기도 제일 쉬웠던 곳이 바로 이 블로그였다. 진짜 천재적이라고 느껴지는 게 dfs를 bool로 만들어서 재귀로 탐색함과 동시에 맞다 아니다 체크까지 할 수 있게 만든 것이... 나는 생각지도 못할 뿐만 아니라 처음엔 이해도 못했다. 왜 저렇게?

 

처음에 ICN에서 시작해서 ICN 뒤에 묶여있는 문자열을 찾아 이동한다. 그리고 이 과정을 반복을 하기 위해 재귀를 하는데 이 과정에서 다른 경로로 가는 것을 막기 위해 다시 한 스텝 더 나간 값을 T/F로 체크해서 제대로 잘 갔으면 그대로 계속하고 아니라면 백트래킹부분, 즉 다시 돌려서 다른 맞는 방향을 찾아가게 하는 것이다!!

 

3. 코드 설명

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int visit[10000] = { };
vector<string> answer;

bool dfs(vector<vector<string>> tickets, string s, int idx)
{
    int i;
    
    if (idx == tickets.size())
        return true;
    
    for (i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == s && visit[i] == 0)
        {
            visit[i] = 1;
            answer.push_back(tickets[i][1]);
            if (dfs(tickets, tickets[i][1], idx + 1)) return true;
            visit[i] = 0;
            answer.pop_back();
        }
    }  
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    int i, idx;
    
    sort(tickets.begin(), tickets.end());

    answer.push_back("ICN");
    dfs(tickets, "ICN", 0);
    
    return answer;
}

 

사전 순으로 이동하기 위해 미리 sort를 사용해 정렬한 후 ICN부터 시작한다.

dfs 함수는 bool 형태로 맞는 경로로 갔으면(모든 항공권을 사용해서 도착했으면) true, 아니면 false를 return 한다.

idx는 tickets배열을 한 바퀴 잘 돌았는지 체크해주기 위해 사용한다. (한 바퀴 잘 돌았어야 문제를 맞게 푼 것이기 때문에)

조건에 맞춰서 반복문을 돌면서 제대로 된 경로로 갔는지 체크하기 위해서 if문으로 확인하고 맞으면 true를 반환해 백트래킹 과정을 진행하지 않고 잘못 간 경우 다시 되돌려서 맞는 방향을 찾아가게 해 준다.

 

+

내가 짰었던 테케 1번 말고 다 돌아가던 코드....

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool check(vector<vector<string>> tickets, string s, int idx, int visit[])
{
    for (int i = 0; i < tickets.size(); i++)
        if (i != idx && tickets[i][0] == s && visit[i] == 0)
            return true;
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    int i, j, idx, visit[10000] = { };
    
    sort(tickets.begin(), tickets.end());
    
    for (i = 0; i < tickets.size(); i++)
    {
        if (tickets[i][0] == "ICN")
        {
            if (check(tickets, tickets[i][1], i, visit))
            {
                visit[i] = 1;
                idx = i;
                answer.push_back(tickets[i][0]);
                answer.push_back(tickets[i][1]);
                break;
            }
        }
    }
    
    while(1)
    {
        int f = 0;
        for (i = 0; i < tickets.size(); i++)
            if (visit[i] == 0)
                f++;
        if (f == 0)
            break;
        
        for (i = 0; i < tickets.size(); i++)
        {
            if (tickets[i][0] == tickets[idx][1] && visit[i] == 0)
            {
                if (check(tickets, tickets[i][1], i, visit) || f == 1)
                {
                    visit[i] = 1;
                    idx = i;
                    answer.push_back(tickets[i][1]);
                    break;
                }
            }
        }         
    }
    
    return answer;
}

 

[["ICN", "AOO"], ["AOO", "BOO"], ["BOO", "COO"], ["COO", "DOO"], ["DOO", "EOO"], ["EOO", "DOO"], ["DOO", "COO"], ["COO", "BOO"], ["BOO", "AOO"]]

["ICN", "AOO", "BOO", "COO", "DOO", "EOO", "DOO", "COO", "BOO", "AOO"]

 

이 반례에 걸려서 문제를 아예 뒤집게 되었다...