프로그래머스 코테 연습 : DFS/BFS - 여행경로 C++

 

 

풀이

1. 초기 접근

• 문제 조건 해석
  • 연속된 경로 출력 -> DFS 문제다.
  • 주어지는 공항 수 n이 3 이상 10000 미만 -> O(n^2) 으로 해결가능하다.
  • 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로가 정답 -> 정렬 작업이 필요하다.

• 코드

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

using namespace std;

const int MAX = 10001;

void dfs(string from, vector<vector<string>>& tickets, bool *visited, vector<string>& answer ){
    answer.push_back(from);
    
    for(int i = 0; i < tickets.size(); i++){
        if(tickets[i][0] == from && visited[i] == false){
            visited[i] = true;
            dfs(tickets[i][1], tickets, visited, answer);
            return;
        }
    }
    
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    
    bool visited[MAX] = {false};
    // 오름차순정렬
    sort(tickets.begin(), tickets.end());
    dfs("ICN", tickets, visited, answer);
    
    return answer;
}

 

2. 오류

이 문제를 풀때 두가지 문제가 발생했다. 

• 문제를 잘못 이해
• 배열, vector의 이해 부족

 

먼저,

1) 문제 조건 해석 오류 

1번의 문제를 잘못 이해한것은 내가 당연히 어떤경로로가든 정답이라고 생각한 것이다. 

그래서 처음의 코드는 그리디처럼 sort로 오름차순 정렬을 하고 시작했다. 그런데

만약,

• 1->2
• 1->3
• 1->4
• 3->4
• 4->2

이렇게 경로가 주어진다면 내가 잘못 짠 코드의 답은 1->2가 된다. 하지만 답은 1->3->4->2가 되어야한다.

 

문제를 다시 보면 

"주어진 항공권을 모두 사용해서" 라고 되어있다.

또한, "모든 도시를 방문할 수 없는 경우는 주어지지 않는다"고 되어있다. 

이 말은 .. 두가지로 생각할 수 있다. 

          1) 모든 도시를 방문하는 경우만 주어진다.

          2) 하나의 도시라도 방문할 수 없는 경우는 주어지지 않는다. 

여기서 맞는 말은 2)다.

따라서,

정답은 모든 도시를 방문해야하고,

모든 도시를 방문하는 것은 주어진 경로의 갯수와 들르는 도시의 갯수가 일치하는 것으로 체크할수 있다.

 

 

2) 배열, vector의 이해 부족

배열을 다른 함수로 전달할 때 주소 전달만 가능하다. 값 전달은 불가능한다. 

일반적으로 값을 전달하는 것은 특정 값을 복사 하는 경우지만 이렇게 주소값으로

 

&로 받으면 원래거를 별명으로 다르게 부르는것이고,

*로 받으면 변수하나를 정의하고 그 원래 주소값을 가져와서 포인터로 기존의 값을 변경하기 위함이다.

 

배열이든 vector든 함수로 전달할때 이렇게만 되게 함으로써 반강제적으로 메모리 낭비를 줄인다.

결론적으로 &가 붙으면 별명이고, *가 붙으면 포인터다.

결국 이 둘은 기존것과 독립되는 것을 복제해서 사용 하는 것이 아니고, 기존것을 가리키는 것이 된다. 

 

 

3. 정답

dfs 재귀로 풀기 때문에 성공일 때 return을 하도록 한다. 

때문에 return의 전과 후의 차이가 있어야한다. return 다음으로 간다는 것은 성공이 아니란 소리니까 return 전에 해주었던

visited 처리와 tmp 벡터에 담았던 현재 경로의 시작도시 등을 다시 복구해놓아야한다. 또한, sort 처리를 해주고 들어가기 때문에 성공적인 경로가 여러개여도 당연히 알파벳순서로 앞서는 경로가 선택된다. 

• 수정한 코드

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

using namespace std;

const int MAX = 10001;

bool dfs(string from, vector<vector<string>>& tickets, bool *visited, vector<string>& tmp, vector<string>& answer, int cnt){
    
    // tmp에 들른 도시를 담는다.
    tmp.push_back(from);
    
    // 모든 도시를 들렀다면 
    if(cnt == tickets.size()){
        return true;
    }
    
    for(int i = 0; i < tickets.size(); i++){
        // 갈수 있는 도시라면 
        if(tickets[i][0] == from && visited[i] == false){
            // 해당 경로(도시아님)를 방문처리한다.
            visited[i] = true;
            bool success = dfs(tickets[i][1], tickets, visited, tmp, answer, cnt+1);
            // 모든 경로를 들러서 모든 도시를 방문했다면
            if(success){
                // answer에 tmp를 담음
                answer = tmp;
                return true;
            }
            // 모든경로를 다 돌지 못하는 경우이다.
            // 이 경로는 이 경우엔 불가능이지만 다른 경우에선 
            // 모든경로를 다 도는 경우의 경로에 포함 될 수 있으므로 
            // 방문을 다시 false 처리한다.
            visited[i] = false;
            
        }
    }
    // 모든 도시를 다 돌지 못하는 경우면 for문안에서 return되지 못하고
    // 여기로 나오게된다.
    // tmp에 push_back 했던 도시를 다시 뺀다.
    tmp.pop_back();
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer, tmp;
    
    bool visited[MAX] = {false};
    // 오름차순정렬
    sort(tickets.begin(), tickets.end());
    // ICN을 시작으로 dfs 시작
    dfs("ICN", tickets, visited, tmp, answer, 0);
    
    return answer;
}

• 모든 경로를 다니면서 모든도시를 방문한 경우 처리부분 (성공일때)

if(success){
    // answer에 tmp를 담음
    answer = tmp;
    return true;
}

• 모든 경로를 다니면서 모든도시를 방문하는 경우가 아닐때 (실패일때)

for(int i = 0; i < tickets.size(); i++){
        ...
        ...
        (성공일 경우 return 처리)
        visited[i] = false;
    }
}
tmp.pop_back();
return false;