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

[문제]

9205번: 맥주 마시면서 걸어가기 (acmicpc.net)

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

[문제 풀이]

home에서 출발해서 거리가 1,000이하가 될때까지 갈수있는 편의점을 들리다가 rock 페스티벌 장소에 거리가 1,000이하가 되면 happy를 아니면 sad를 출력하는 문제이다.

 

BFS를 이용해서 해당 문제를 풀도록 하자.

home의 위치를 큐에 넣어주고 해당 큐에서 편의점 0번부터 n -1 번까지 돌아다니면서 아직 방문하지 않았고 거리가 1,000이하라면 해당 편의점을 큐에 넣어주자.

그렇게 해당 위치에서 갈수 있는 곳을 모두 넣었다면 다음 위치에서 이를 반복하면서 rock 페스티벌에 도착할 수 있다고 나오면 happy 큐의 크기가 0이 될때까지 도달할 수 없으면 sad를 출력하자.

[회고]

어렵지 않은 문제였지만 visited 부분에서 2번이나 실수를 해서 틀렸다.

첫번째로는 visited 초기화를 안한것을 잊고 제출을 하였다가 틀렸고 두번째로는 벡터로 만들었다가 .clear() 함수로 아예 초기화를 해버려서 틀렸다. clear() 함수는 초기화 함수이지 0으로 모두 채우는 함수가 아닌것에 주의하도록 하자.

[코드]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int visited[101];

void visitClear(){
    for(int i = 0;i<101;i++){
        visited[i] = 0;
    }
    return;
}

bool isReach(pair<int,int> cur, pair<int,int> next){
    bool answer = false;
    if((abs(cur.first - next.first) + abs(cur.second - next.second)) <= 1000){
        answer = true;
    }
    return answer;
}

int main(){
    int testcase;
    cin>>testcase;

    for(int T = 0; T < testcase; T++){
        visitClear();
        int n;
        cin>>n;
        vector<pair<int,int> > convenience(n);
        //시작 위치

        pair<int,int> home;
        cin>>home.first>>home.second;
        
        //편의점들 위치
        for(int i = 0;i<n;i++){
            cin>>convenience[i].first>>convenience[i].second;
        }

        //도착 위치
        pair<int,int> rock;
        cin>>rock.first>>rock.second;

        queue<pair<int,int> > q;
        q.push(home);
        bool flag = false;

        while(q.size() > 0){
            pair<int,int> cur = q.front();
            q.pop();
            if(isReach(cur,rock) == true){
                flag = true;
                break;
            }
            for(int i = 0;i<n;i++){
                if(visited[i] == 0 && isReach(cur,convenience[i]) == true){
                    visited[i] = 1;
                    q.push(convenience[i]);
                }
            }
        }

        if(flag == false){
            cout<<"sad"<<endl;
        }
        else{
            cout<<"happy"<<endl;
        }

        //1. 현재 위치에서 rock까지 1,000이하인지 확인.
        //2. 아니라면 가장 가까운 편의점중 갈 수 있는 곳들 모두 방문하기.
        
    }
    return 0;
}