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

 

나름 기발하게 풀었다고 생각했는데

맙소사, 찾아보니 다른분들도 다 똑같이 푸셨다.

 

 

Key Point

 모두 하나의 자료구조에 저장한다.

 

 집좌표 = 인덱스 0에 저장됨

 편의점좌표 = 인덱스 1 ~ N에 저장됨

 페스티벌좌표 = 인덱스 N + 1에 저장됨

 

 이렇게 하면 방문처리도 2차원 배열로 구성하지 않아도 가능하다.

 2차원 배열로 VISIT처리를 하면 공간복잡도도 폭발하고, 시간복잡도도 폭발한다.

 

 

 

BFS와 유사하게, 큐를 이용하여

도달 가능한 것들을 큐에 넣어주면서 반복 진행한다.

 

큐에 페스티벌좌표가 들어갔다면 happy, 아니면 sad

 

/*
 
 단순 뺄셈 연산으로 풀어나갈 수 있을 것 같은데.
 
 시작점에서 도달 가능한 것들 push
 
 push 된 것 중에서 도달 가능한 것들 push...
 
 push한 것 중에 끝지점 있으면 합격
 
 
 x s x x
 x x x x
 x c c x
 x x x x
  
 */

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

using namespace std;

int T, N;

bool VISIT[102]; // 100개 편의점 + 1개 집 + 1개 페스티벌


int main() {
    
    int x, y;
    
    cin >> T;
    
    
    while(T--) {
        
        vector<pair<int, int>> coordinates; // 모든 좌표는 여기에.
        queue<pair<int, int>> que; // 방문을 처리하는 큐

        bool flag = false;
        memset(VISIT, 0, sizeof(VISIT));
        
        
        cin >> N; // 편의점 수
        
        cin >> x >> y; // 집 좌표
        
        // 집 좌표 벡터에 삽입
        coordinates.push_back({x, y});

        // 집 좌표 큐에 삽입
        que.push({x, y});
        VISIT[0] = true; // 방문처리
        
        // 편의점 입력받아서 벡터에 삽입
        for(int i = 0; i < N; i++) {
            cin >> x >> y;
            
            coordinates.push_back({x, y});
        }
        
        // 페스티벌 좌표
        cin >> x >> y;
        coordinates.push_back({x, y});
        
        
        
        while(!que.empty()) {
            
            
            int x = que.front().first;
            int y = que.front().second;
            
            que.pop();
            
            
            for(int i = 0; i < N + 2; i++) {
                
                if(!VISIT[i]) {
                    
                    int distance = abs(x - coordinates[i].first) + abs(y - coordinates[i].second);
                    
                    if(distance <= 1000) {
                        
                        que.push({coordinates[i].first, coordinates[i].second});
                        VISIT[i] = true;
                        
                        if(i == N + 1) { // 페스티벌 좌표가 들어갔다면, 성공했으므로 종료
                            flag = true;
                            break;
                        }
                    }
                    
                }
                
            }
            
        }
        
        if(flag)
            cout << "happy\n";
        else
            cout << "sad\n";
        
    }
    
}

 

 

소요 시간 : 30분