[백준/C++] 9205번: 맥주 마시면서 걸어가기

맥주 마시면서 걸어가는게 참 힘든 일이라는 것을 깨닫게 된 날이다.. 이문제 뭔데 어렵냐ㅠㅠㅠ이해하는데 너무 오래걸려서 자괴감이 들지만 모르는 걸 하나 알게 되었다는 것에 감사하도록 하자.

 

이 문제의 경우 그래프가 주어지지 않았다. 그래서 직접 그래프를 만들어야 하는데 어떻게 만들어야 할 지 감이 잘 안왔다. 노드의 배열에 이런식으로 간선을 추가해본 적이 없어서 더 어려웠다. 결론적으로 정석풀이들을 참고하여서 코드를 완성했고 따라 쓰면서 이해한 정도다.

 

1) 메모리초기화

2) pair자료형의 벡터로 집 , n개의 편의점, 페스티벌 이렇게 n+2개를 입력으로 받는다.

3) 그래프를 생성한다.

 - 현재 노드로 부터 앞으로 갈 수 있는 노드에 대해서 모두 버틸 수 있는 거리라면 연결된 노드로 추가한다.

 - 여기서 20개는 50m에 한잔 씩 마시므로 1000m가 버틸 수 있는 거리가 된다.

 - 양방향 모두 추가해준다.

4) 탐색을 한다.

 - 내 노드의 모든 연결된 노드들을 확인하고 방문하지 않은 노드라면 그 노드에 가서 다시 dfs돌린다.

5) 탐색이 끝났을 때 페스티벌노드(n+1번째 노드)가 방문되었다면 happy 아니면 sad출력

 

벡터 배열은 처음 써봐서 신기하다. 이런 좋은 기법이...

 

#include<iostream>
#include<vector>
#include<algorithm>
#include <cstring>

using namespace std;

vector<int> map[102];
int visit[102];

void initial() {
    for (int i = 0; i < 102; i++) {
        map[i].clear();
    }
    memset(visit, false, sizeof(visit));
}

int Manhatten(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

void dfs(int node) {

    visit[node] = 1;
    for (int i = 0; i < map[node].size(); i++) {
        int next = map[node][i];
        if (visit[next] != 1) {
            dfs(next);
        }
    }
}

int main() {

    int test_case;
    cin >> test_case;

    for (int i = 0; i < test_case; i++) {

        //초기화 단
        initial();

        // 입력 단: 출발 + n개의편의점 + 도착 
        int nConvi;
        vector<pair<int, int>> v;
        cin >> nConvi;
        for (int j = 0; j < nConvi+2; j++) {
            int a, b;
            cin >> a >> b;
            v.push_back(make_pair(a, b));
        }

        // 그래프 생성 단
        for (int j = 0; j < nConvi + 2; j++) {
            for (int k = j + 1; k < nConvi + 2; k++) {
                if (Manhatten(v[j], v[k]) <= 50 * 20) {
                    map[j].push_back(k);
                    map[k].push_back(j);
                }
            }
        }
        /* 디버깅
        for (int p = 0; p < nConvi + 2; p++) {
            for (int q = 0; q < map[p].size(); q++) {
                cout << map[p][q] << " ";
            }
            cout << endl;
        }
        */

        // 처리 단 : 0번노드부터
        dfs(0);


        // 출력 단
        if (visit[nConvi + 1])cout << "happy\n";
        else cout << "sad\n";

    }


    return 0;
}