BOJ 9205 맥주 마시면서 걸어가기 - Tue, Nov 17, 2020

BFS로 풀었지만 다음에는 플로이드-와샬로 풀어보자.

BOJ 9205 는 길찾기 문제이다. 정해진 기간마다 맥주를 마시면서 걷다 맥주가 부족해지기 전에 가게에 들려 맥주를 리필하고, 목적지를 찾아갈 수 있는지 여부를 출력해주면 된다.

풀이

맥주가 떨어지기 전에 갈 수 있는 최대거리는 1000미터이므로 BFS를 이용해서 1000미터 이내의 슈퍼를 방문하고 목적지까지 갈 수 있는지 여부를 확인하는 방법을 풀었다.

using namespace std;

bool canWalk(pair<int,int> &a, pair<int,int> &b) {
    return abs(a.first - b.first) + abs(a.second - b.second) <= 1000;
}

void bfs(vector<pair<int,int>> &a) {
    vector<bool> visited(a.size());
    queue <int> q;
    q.push(0);

    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        visited[curr] = true;
        for (int i = 1; i < a.size(); i++) {
            if (!visited[i] && canWalk(a[curr], a[i])) {
                if (i == a.size() - 1) {
                    cout << "happy\n";
                    return;
                }
                q.push(i);
            }
        }
    }
    cout << "sad\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        vector<pair<int, int>> a(n + 2);

        for (int i = 0; i < n + 2; i++) {
            cin >> a[i].first >> a[i].second;       
        }

        bfs(a);        
    };
    
    return 0;
}

회고

• 왜맞틀(왜 맞았는데 틀렸다고 하지?)가 나왔는데 각 테스트케이스마다 초기화를 잊었다. 실수하지 말자.
• BFS를 예전보다 좀 더 빠르게 구현하게 되었다. 하지만 여전히 약간씩 실수하는 경향이 있다.

TODO

• 다익스트라나 플로이드-와샬로 풀어보자. 예전에는 두 알고리즘을 종종 사용했었는데, 최근에는 더 구현이 쉬운 BFS나 DFS로 풀리는 문제는 둘 중 하나로 풀 다 보니 빠른 구현이 어려워졌다.
• 문제를 풀기 전에 복잡도를 생각해 보는 연습도 필요한 것 같다.

다른 풀이

• 구글링으로 나온 블로그