240216: 여행경로 문제 재귀 DFS 해결, 일정

2024-02-16

오늘은 약속이 있어서 공부를 많이 하지 못한다.
머리도 식힐겸..)

• 프로그래머스 여행경로 문제를 풀었다.
• 백준 브론즈 한 문제를 풀었다. 스트릭 :(
• 일정이 있어서 공부를 많이 하지 못했다.

오늘의 프로그래머스

- 깊이/너비 우선 탐색(DFS/BFS)
여행경로 (Lv. 3)

여행경로

여행 경로는 주어진 항공 티켓을 모두 소모하는 여행 경로를 짜는 문제로, 가능한 경로가 두개 이상이라면 알파벳순으로 경로를 짜야한다.

어제 재귀 DFS와 스택 DFS의 차이에 대해 느꼈던 문제다.

재귀는 삽입된 순서대로 바로 바로 탐색하면서 왼쪽 분기부터 타고 내려가는데, 스택은 삽입된 순서의 역순으로 탐색하기 때문에 오른쪽 분기부터 타고 내려가서, 위 문제의 **항상 알파벳 순으로 앞서는 경로여야한다** 라는 문제 조건을 지키려고 알파벳 순으로 조건에 맞는 걸 탐색하면서 스택에 추가하도록 구현 했는데,  이렇게 결국에 알파벳 순으로 탐색을 해봤자, 스택으로 구현하면 해당 분기에서 알파벳 순으로 추가된 노드들을 역순으로 탐색해서 추가적인 로직 구현이 더 필요하기 때문에. 스택오버플로우가 걱정되는게 아니면 재귀로 구현하는 게 편하다.

Stack으로 구현할 때 Massive하게 조건 충족하는 것들을 한번에 stack.push()해서, 원하던 알파벳 순이 꼬일 수 있었다. 같은 분기에서 stack.push()를 2개 이상 하면, 다음 분기에서 제일 마지막에 push된 스택 먼저 실행되기 때문이다.

따라서, 어제의 Stack 코드를 갈아 엎고 Recursive DFS로 다시 구현하였다.
코드가 훨씬 직관적이게 되었다.

vector<string> dfs(vector<bool>& visited, vector<string>& route, vector<vector<string>>& tickets, int index) {
    if (route.size() == tickets.size()) {
        route.push_back(tickets[index][1]);
        return route;
    }

    string current_city = tickets[index][0];
    string next_city = tickets[index][1];

    for (int i=0;i<tickets.size();++i) {
        if (!visited[i] && tickets[i][0] == next_city) { // 다음 경로를 찾음
            visited[i] = true;
            route.push_back(next_city);
            vector<string> result = dfs(visited, route, tickets, i);
            if (!result.empty()) {
                return result;
            }
            visited[i] = false;
            route.pop_back();
        }
    }

    return {};
}

vector<string> solution(vector<vector<string>> tickets) {
    sort(tickets.begin(), tickets.end());
    vector<string> route;
    route.push_back("ICN");
    for (int i=0;i<tickets.size();++i) {
        if (tickets[i][0] == "ICN") {
            vector<bool> visited(tickets.size());
            visited[i] = true;
            dfs(visited, route, tickets, i);
        }
    }

    return route;
}

경로를 찾다가 답이 안나오면 이전 상태로 모두 백트래킹한다.
가능한 경로가 한개도 없는 TC는 출제되지 않음으로 해당 사항은 고려 제외.

---

퍼즐 조각 채우기

해당 문제는 보드의 빈칸 정보가 주어지면 퍼즐 조각을 알맞게 채워야 하는 문제로, 오늘은 어떻게 접근할지 아이디어만 고민하고 내일 풀도록 하겠다.

오늘은 공부를 많이 하지 못했다.
내일, 그리고 전주로 돌아가서 많이 해야겠다!

최종 평가

오늘의 학습 성과:
- 프로그래머스 여행경로 문제 해결
- 백준 브론즈 문제 해결

학습 성취:
1. **여행경로 문제 해결**: 어제 스택 DFS와 재귀 DFS의 차이를 명확히 인지하고, 오늘은 재귀 DFS로 문제를 해결하여 코드의 직관성과 효율성을 높였습니다. 이 과정에서 스택과 재귀의 사용법에 대한 이해를 깊게 하였으며, 알고리즘의 선택이 문제 해결 과정에서 얼마나 중요한지를 다시 한번 깨달았습니다.

2. **알고리즘 효율성 개선**: 여행경로 문제의 해결을 통해 복잡한 문제에 대한 접근법을 재고하고, 보다 효율적인 해결 방안을 찾아내는 능력을 발휘했습니다. 재귀를 통해 간결하고 이해하기 쉬운 코드로 문제를 해결함으로써, 알고리즘 문제 해결 능력을 한 단계 발전시켰습니다.

3. **퍼즐 조각 채우기 문제 접근**: 아직 해결하지는 않았지만, 문제에 대한 접근 방법과 아이디어를 고민하는 시간을 가짐으로써, 문제 해결 전략을 세우는 능력을 강화하였습니다. 이는 복잡한 문제에 대한 체계적인 접근과 해결 과정에서의 창의적 사고를 발전시키는 데 도움이 될 것입니다.

평가 및 피드백:
오늘은 약속으로 인해 학습 시간이 제한되었음에도 불구하고, 중요한 문제 하나를 해결하는 데 집중하여 성공적으로 완료했습니다. 이는 시간 관리와 학습 목표 설정의 중요성을 다시 한번 상기시켜 줍니다. 앞으로도 주어진 시간을 최대한 활용하여 학습 효율을 극대화할 필요가 있습니다.

추가적으로, 문제에 대한 다양한 접근 방법을 고민하고, 이를 통해 가장 적합한 해결책을 찾아내는 과정은 알고리즘 문제 해결 능력을 향상시키는 데 매우 중요합니다. 계속해서 다양한 문제를 해결해나가면서 이러한 능력을 지속적으로 강화해 나가길 바랍니다.

학습 성과 평가 점수: 80/100
- 주어진 시간 동안 여행경로 문제를 해결하며 알고리즘 문제 해결 능력을 발휘한 점에서 긍정적인 평가를 받았습니다. 하지만, 학습 계획의 전체적인 완성도를 높이기 위해서는 더 많은 문제를 해결하고, 학습 범위를 다양화할 필요가 있습니다.

향후 개선 방안:
- 학습 시간이 제한적일 때는 학습 목표를 구체적으로 설정하고, 이를 달성하기 위한 전략을 사전에 계획하는 것이 중요합니다.
- 다양한 알고리즘 문제에 도전하면서, 문제 해결 과정에서의 다양한 접근 방법과 알고리즘을 실험해 보는 것이 중요합니다. 이를 통해 더 넓은 범위의 문제에 대한 해결 능력을 키울 수 있습니다.