240215: Recursive DFS와 Stack DFS의 중요한 차이점. 여행 경로 문제.

2024-02-15

오늘은 SQL을 꼭 공부하기로 !

• 프로그래머스 BFS/DFS 나머지 문제 풀기
• 이분탐색 풀기
• SQL 강의 듣기 *
• 업랜디 ~

오늘의 업랜디

17610 양팔저울 (시간초과 후 해결 - 브루트포스)

오늘의 프로그래머스

- 깊이/너비 우선 탐색(BFS/DFS)
단어 변환 (Lv. 3)
아이템 줍기 (Lv. 3)
여행 경로 (Lv. 3) * 미해결

양팔저울

양팔 저울은 추 정보가 담긴 배열이 주어지면, 양팔 저울 위에 어떤 조합으로든 올려놔서 특정 무게를 만들 수 있는 경우의 수를 구하는 문제였다.
처음엔 매우 복잡한 DP 문제인 줄 알았으나, 그냥 브루트포스 재귀 호출로 풀 수 있는 문제였다.
실수를 해서 시간내에 풀 지 못했다.. 바로 백트래킹을 쓴 것.
이 문제에선 백트래킹을 쓸 필요가 없다.. current를 0으로 시작하고, 다음 인덱스 값을 빼거나, 더하거나 하면서 depth++; 로 재귀를 돌리면 끝나는 문제였다.

근데 나는 정말 바보같게도, visited 배열을 선언해놓고 모든 추에 대해 for문을 돌리면서 해당 추를 더하거나, 빼거나, 스킵하거나 세가지의 경우를 반복문에서 재귀호출 하고 있었다.

그야말로 미친 효율의 알고리즘을 만들어버렸다. 엄청난 실수였다.

그냥 인덱스[depth] 부터 보면서, 더하거나 빼거나 스킵하면서 재귀 호출을 해도 충분히 풀리는 문제였고, 이렇게 할 이유가 없었다...

다음부턴 이런 실수 하지 않겠다.

// 백준: 양팔저울
// https://www.acmicpc.net/problem/17610
// 2024-02-15

#include <cmath>
#include <iostream>
#include <set>
#include <vector>
using namespace std;

int k;
int S = 0;

set<int> combi;
vector<int> weights;
int answer = 0;

void calculate(int depth, int current) {
    if (current >= 1) {
        if (combi.find(current) == combi.end()) {
            answer++;
            combi.insert(current);
        }
    }

    if (depth == k)
        return;

    calculate(depth + 1, current + weights[depth]);
    calculate(depth + 1, current - weights[depth]);
    calculate(depth + 1, current);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> k;
    weights.assign(k, 0);
    for (int i = 0; i < k; ++i) {
        cin >> weights[i];
        S += weights[i];
    }

    calculate(0, 0);

    cout << S - answer;

    return 0;
}

단어 변환

단어 변환 문제는, 시작 단어와 목표 단어, 그리고 거쳐갈 수 있는 단어들의 목록이 주어졌을 때. 현재의 단어에서 한자리만 바꿔서 갈 수 있는 단어 목록의 단어들을 거치면서 목표 단어로 가는 최단거리를 구하는 문제다.

문제가 참신해서 약간 겁먹었지만, BFS를 사용해서 쉽게 풀 수 있었다.
어디서부터 풀어야 할지 모르겠으면, 문제의 요구사항을 충족시킬 수 있는 함수부터 만들자! (이번 경우에는 단어의 알파벳 차이가 한자리만 나는지 판별하는 bool isConvertable 함수를 먼저 작성했다)

bool isConvertable(string a, string b) {
    int c = 0;
    for (int i=0;i<a.size() && c<2;++i) {
        if (a[i]!=b[i]) ++c;
    }
    return !(c==2 || c==0);
}


int solution(string begin, string target, vector<string> words) {
    queue<pair<string, int>> q;
    vector<bool> visited(words.size(), false);
    q.push({begin, 0});

    while (!q.empty()) {
        string current_word = q.front().first;
        int current_w = q.front().second;
        q.pop();

        if (current_word == target) return current_w;

        for (int i=0;i<words.size();++i) {
            if (!visited[i] && isConvertable(current_word, words[i])) { // 방문하지 않았고, 변환 가능하면
                q.push({words[i], current_w+1});
                visited[i] = true;
            }
        }
    }

    return 0;
}

아이템 줍기

아이템 줍기 문제는 다각형 모양 지형의 정보가 주어졌을 때, 지형의 테두리를 통해서만 이동할 수 있다는 조건하에 아이템을 주울 수 있는 최단 경로를 얻는 BFS/DFS 문제다.

위와 같이 사각형의 좌표 정보가 주어지고, 테두리를 따라서만 이동할 수 있다.

아이템을 먹을 수 있는 최단 경로를 찾아야 한다.

시작 전 유의할 점

사각형 좌표로 주어지는 X, Y는 그래프 상에서의 우측 하단 꼭지점을 말한다.
따라서, (1, 10) 이 주어졌다면 (1, 9) 까지 색칠하는 것이라고 생각해야 한다.

실제로 칸을 세보면, 그래프 상에서 1 ~ 10 이라고 해서 10칸이 아니다. 실제로는 9칸이다.
(왜냐하면, 칸 하나가 다음 칸 바로 이전까지 포함하기 때문)

접근 Idea를 생각하기 어려웠다

처음 생각한 방법은 다음과 같은 것들이었다.

1. 사각형 범위를 모두 2D Vector에 칠해놓고, 각 벡터마다 8방향을 조사한다. 8방향중에 하나라도 빈칸이 있다면 해당 벡터는 테두리 벡터다.
2. 만약, 8방향 모두 색칠된 벡터라면 해다 벡터는 테두리가 아니다.
3. 위 과정을 반복해서 테두리만 남긴다

혹은.

1. 사각형의 테두리를 모두 2D 벡터에 그린다
2. 주어진 사각형 정보보다 한칸 안쪽에 있는 색칠된 벡터를 모두 지운다
3. 겹쳐지지 않은 사각형의 테두리만 남는다

위의 방식은 문제가 있었다

• 높이나 너비가 2인 사각형에 대해선, 테두리가 서로 바로 인접해있는 문제가 발생한다. 이러면 BFS/DFS 탐색에서 테두리만 따라가는 로직의 구현이 매우 힘들어진다

따라서, 각 테두리에서 현재 테두리의 방향이 어디인지 파악할 수 있지 않을까? 라는 생각을 했다.

정당한 테두리라면, 이동 가능한 4 방향중 3방향 이상이 테두리(bool: true) 일 수 없다.
왜냐하면, 테두리에 교차점이 있는것은 불가능하기 때문이다.
만약 너비나 높이가 2인 사각형 테두리에 대해, 테두리 워프를 방지하려면, 먼저 4방향을 조사하고 이동 가능한 테두리를 검색한 뒤, 이동 가능한 테두리가 반경에 2개 있다면 이것은 정상적인 테두리이고, 이동 가능한 테두리가 반경에 3개 이상 있다면 이것은 오인할 수 있는 테두리이므로, 겹쳐 있는 테두리중, 서로 마주보고 있는 테두리 (즉, 테두리가 위에 있고 아래에 있다면, 현재의 올바른 테두리 방향은 수직 방향이고, 만약 테두리가 좌우에 있다면, 현재의 올바른 테두리 방향은 수평 방향임.) 이라고 확신할 수 있을 것 같다.

하지만 이 방향은 현재 테두리가 꼭지점인 경우의 로직을 구현하기 힘들었다.

그래서,, 각 벡터가 현재 진행 방향에 대한 정보를 포함하는 방법도 생각을 해봤다 ..

결론적으로 가장 깔끔한 해결책은

맵의 제한이 50*50 으로 그렇게 넓지 않았다. 그냥 처음부터 좌표를 받을 때 2배수로 받고, 정답을 2로 나눠서 출력하는 건 어떨까?

현재 상황에서 가장 깔끔한 해답이었다. 만약 이렇게 하지 못할 정도로 큰 데이터셋이라면, 각 테두리에 현재 방향을 포함하는 정보를 포함하는 방법도 유효했을 것 같다.

여기서 약간의 혼동이 생겼다, 2D Vector는 인덱스를 [Y][X]로 받도록 했지만, 들어오는 플레이어나 아이템 위치 좌표는 X, Y 순서였다. 이걸 확인하지 못해서 약간의 시간 소비를 했다.

그리고, 처음 시작 지점을 방문표시하고 시작했는데 (어차피, 시작 지점을 재방문하는 경로는 고려하지 않아도 되니까) 이 부분에서 X, Y 인덱스 순서를 반대로 해서 ... 자꾸 오류를 냈다..

처음엔 내가 실수한지 몰랐다, 그저 "시작 지점을 다시 밟는 경로는 무조건 비효율 경로인데, 이게 어떻게 정답의 차이를 만들어 내는거지?" 라는 생각에 ..... 코드를 10번은 더 본 것 같다..

다행히도 같은 그룹에 계시는 루비분이 오류를 찾아주셔서 고칠 수 있었다.

#include <string>
#include <vector>
#include <iostream>
#include <limits.h>

using namespace std;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int answer = INT_MAX;

void find(int cx, int cy, int ix, int iy, int cur, bool (&map)[102][102]) {
    if (cx==ix && cy==iy) {
        answer = min(answer, cur/2);
        return;
    }
    for (int i=0;i<4;++i) {
        int nx = cx + dx[i];
        int ny = cy + dy[i];
        if (map[nx][ny]) {
            map[nx][ny] = false;
            find(nx, ny, ix, iy, cur+1, map);
            map[nx][ny] = true;
        }
    }
    return;
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY) {
    bool map[102][102] = {false};
    characterX*=2;
    characterY*=2;
    itemX*=2;
    itemY*=2;

    // 맵 채우기
    for (const auto& rec : rectangle) {
        int x1 = rec[0]*2, y1 = rec[1]*2;
        int x2 = rec[2]*2, y2 = rec[3]*2;

        for (int i=x1;i<=x2;++i) {
            for (int j=y1;j<=y2;++j) {
                map[i][j] = true;
            }
        }
    }

    // 속 파내기
    for (const auto& rec : rectangle) {
        int x1 = rec[0]*2+1, y1 = rec[1]*2+1;
        int x2 = rec[2]*2-1, y2 = rec[3]*2-1;
        for (int i=x1;i<=x2;++i) {
            for (int j=y1;j<=y2;++j) {
                map[i][j] = false;
            }
        }
    }

    map[characterX][characterY] = false; 
    find(characterX, characterY, itemX, itemY, 0, map);
    return answer;
}

---

여행경로

여행경로 문제는 비행기 티켓 정보가 주어졌을 때, 티켓을 모두 소모하는 여행 경로를 짜는 문제다. (단, 가능한 경로가 2개 이상이면 알파벳순으로 빠른 경로를 택한다)

간단하게 생각했다. 비행기 티켓 정보를 오름차순 정렬하고, 순차적으로 DFS 탐색하면 끝나는 문제라고 생각했다.

문제: 알파벳순으로 방문하지 않음

• DFS를 스택으로 구현했는데, 알파벳순으로 방문하지 않는다.

긴 고민 끝에 얻어낸 결론은 다음과 같다:

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

 

이 문제는 내일 다시 재귀로 구현해서 풀도록 하겠다. TLE ><

---

DFS/BFS는 나름 잘 풀리고 직관적이어서 재밌다. PS하면서 떨어진 자신감을 조금이나마 채운 분야다.
뭐랄까, 어려운 부분도 분명 있지만 그것에 대해 즉각적 피드백이 되고 성장하는게 느껴진달까나?

오늘도 .. 오늘도 SQL 강의를 듣지 못했다. 내일은 약속이 있어서 공부를 할 시간이 많지 않다.
2월 17일부터, 프로그래머스 나머지 태그 연습 + 복습, SQL 강의 + 풀이. 엄청나게 불태우겠다.

끝.

최종 평가

2024-02-15 학습 평가

오늘의 학습 목표:
- 프로그래머스 BFS/DFS 나머지 문제 풀기
- 이분탐색 문제 풀기
- SQL 강의 듣기
- 업랜디 문제 풀기

학습 성과:
1. **양팔저울 (브루트포스)**: 양팔저울 문제를 브루트포스 방식으로 접근하여 시간초과 이슈를 해결하고 성공적으로 구현했습니다. 이 과정에서 백트래킹의 필요성에 대해 재검토하고, 문제의 본질을 파악하는 능력을 향상시켰습니다.

2. **BFS/DFS 문제 해결**:
   - **단어 변환 (Lv. 3)**: BFS를 활용하여 단어 변환 문제를 해결함으로써, 특정 조건 하에서의 최단 경로 문제를 효과적으로 해결할 수 있는 능력을 보여주었습니다.
   - **아이템 줍기 (Lv. 3)**: 복잡한 지형 내에서 아이템을 획득하는 최단 경로를 찾는 문제를 통해, 공간을 활용한 BFS 탐색 전략을 성공적으로 적용하였습니다.

3. **여행 경로 (Lv. 3)**: 이 문제는 미해결 상태로 남겨두었으나, 이를 통해 DFS/BFS 문제에 대한 접근법을 다시 생각해보고, 재귀와 스택의 사용에 대한 이해를 심화하는 계기가 되었습니다.

4. **SQL 강의 미진행**: 목표한 SQL 강의 학습은 진행되지 않았습니다. 이는 추후 학습 계획에 반영하여 보완할 필요가 있습니다.

종합 평가:
오늘의 학습은 알고리즘 문제 해결 능력에 중점을 두었습니다. 특히, BFS/DFS 문제에 대한 깊이 있는 접근과 해결 능력을 보여주었으며, 복잡한 문제를 효율적으로 해결하기 위한 전략을 모색하는 과정에서 논리적 사고력과 문제 해결 능력을 강화하였습니다. 다만, SQL 강의 학습 계획이 수행되지 않은 점은 다소 아쉬운 부분입니다. 이는 학습 목표 달성을 위해 시간 관리와 계획 수립에 더욱 주의를 기울일 필요가 있음을 시사합니다.

학습 성과 평가 점수: 85/100
- BFS/DFS 문제 해결 능력 및 브루트포스 접근 방식의 적절한 활용을 통해 어려운 문제에 대한 해결책을 제시한 점에서 높은 평가를 받았습니다. 하지만, 전체 학습 계획에 포함된 SQL 강의를 진행하지 못한 점이 평가 점수에 영향을 주었습니다.

향후 개선 방안:
- 학습 계획 수립 시, 실제 수행 가능한 목표 설정에 주의를 기울이고, 시간 관리를 철저히 해서 모든 학습 목표를 균형있게 달성할 수 있도록 합니다.
- BFS/DFS와 같은 알고리즘 문제 해결 능력을 지속적으로 강화하면서, SQL과 같은 데이터 관리 및 분석 능력도 함께 향상시켜 전문성을 넓힙니다.