백준 9205 - 맥주 마시면서 걸어가기 - BFS

문제

문제링크 : https://www.acmicpc.net/problem/9205

풀이전략

1. 50미터에 맥주 한병임으로 1000m이전에 편의점 또는 페스티벌이 있어야한다.
2. 먼저 바로 락페스티벌에 참여 가능한지 보고, 그렇지 않다면 주변 편의점 중 갈 수 있는 곳으로 간다.
3. 갈 수 있으면 happy, 갈 수 없으면 sad이므로 사실 BFS이든 DFS이든 상관없지만 그럼에도 이렇게 길이를 구하는 것은 BFS로 해결한다.

코드

#include<bits/stdc++.h>

using namespace std;

// loc이라는 struct을 만든다.
// x는 x좌표 y는 y좌표이다.
struct loc{
    int x, y;
    loc(int a, int b){
        x= a;
        y = b;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    int t;
    int n;
    int ta, tb;
    cin >> t;
    vector<loc> store;
    // 체크배열을 통해 이미 한번 지난 편의점을 다시 지나지 않도록 한다.
    // 싸이클 생성을 막기 위해 -> 물론 있어도 상관없지만, 이렇게 처리하는게 효율적이다.
    bool ch[101];
    for(int tt = 0; tt<t; tt++){
        cin >> n;
        cin >> ta >> tb;
        
        memset(ch, false, sizeof(ch));
        queue<loc> q;
        // 시작 좌표를 큐에 넣는다.
        q.push(loc(ta, tb));

        store.clear();
        for(int i=0; i<n; i++){
            cin >> ta >> tb;
            // 편의점의 위치들을 벡터에 넣어준다. 
            store.push_back(loc(ta, tb));
        }
        cin >> ta >> tb;
        loc end = loc(ta, tb);

        bool flag = false;
        
        while(!q.empty()){
            
            loc ret = q.front();
            q.pop();
            
            int dis = abs(ret.x - end.x) + abs(ret.y - end.y);
            // 페스티벌에 갈 수 있는지 여부
            if(dis <= 1000){
                flag = true;
                break;
            }
            
            // 편의점 가능여부 확인
            // 갈 수 있는 편의점은 큐에 넣어 또다시 확인한다. 
            for(int i=0; i<store.size(); i++){
                dis = abs(ret.x - store[i].x) + abs(ret.y - store[i].y);
                if(!ch[i] && dis <= 1000){
                    ch[i] = true;
                    q.push(store[i]);
                }
            }
        }
        if(flag) cout << "happy"<<endl;
        else cout << "sad"<<endl;
    }
    return 0;
}

소감

처음에는 어떻게 해결해야할지 몰랐으나, 이 문제는 도달이 가능한지 아닌지를 찾는 문제이다. 어떻게 보면 편의점 들을 노드, 페스티벌을 목적지로 생각하고 그래프 탐색을 하는 문제와 같다고 볼 수 있다.