맥주 마시면서 걸어가기 (feat. 백준, 9205번)

맥주 마시면서 걸어가기
https://www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int T, N, ex, ey;
pair<int, int> arr[101];
bool visit[101];
bool bfs(register int x, register int y){
    memset(visit, false, sizeof(visit));
    queue<pair<int, int>> q;
    q.push(make_pair(x, y));
    while(!q.empty()){
        auto p = q.front(); q.pop();
        x = p.first, y = p.second;
        if(abs(x - ex) + abs(y - ey) <= 1000)
            return true;
        for(register int n = 0; n < N; ++n){
            auto tmp = arr[n];
            if(!visit[n] && (abs(x - tmp.first) + abs(y - tmp.second) <= 1000))
                visit[n] = true, q.push(make_pair(tmp.first, tmp.second));
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> T;
    for(register int t = 0, x, y; t < T; ++t){
        cin >> N >> x >> y;
        for(register int n = 0; n < N; ++n)
            cin >> arr[n].first >> arr[n].second;
        cin >> ex >> ey;
        if(bfs(x, y))
            cout << "happy\n";
        else
            cout << "sad\n";
    }
    return 0;
}
// *&)*@*

 

 

1. 시작점으로부터 1000미터만큼 움직일 수 있다는 제약이 있습니다. (편의점 또는 도착점에 들리기까지)
2. 따라서 시작점으로부터 모든 편의점에 대해 bfs 탐색을 진행합니다. 1000미터보다 가까운 편의점이 있다면 해당 편의점 인덱스에 마킹을 하고 queue에 삽입하여 다음 bfs의 아이템으로 소비합니다.
3. 2번을 진행하며 queue에서 가져온 좌표 (x,y)와 도착점 (sx,sy)간의 거리가 1000미터 이하라면 "happy"를 출력하여 종료하고, 모든 너비 우선 탐색이 끝날때까지 종료되지 않았다면 "sad"를 출력하여 종료합니다.