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

문제 추상화

  • 출발점에서 종료점까지 가는데
  • 최대 1000의 거리까지 갈 수 있음
  • 어느 지점 들려서 가면 갈수 있는지 확인

아이디어

  • bfs로 도착지 갈수 있는지확인
    • 그럼 각 점에서 다음 점으로 갈수 있는지는 어떻게 확인?
      • 반경 1000미터를 돌면서 확인하면 되지 않을까?
        • 그러면 정점이 너무 많아짐
        • BFS : O(V+E)
          • V : 모든 정점 : 9e8 > 시간초과
      • 편의점과 펜타포트를 기록해뒀다가 계속 탐색해보자
    • 그래서 펜타포트와 값이 같아지면 종료

시간복잡도 계산

  • 테스트 케이스 O(T)
  • 간선의 개수 : O(N^2)
  • BFS : O(V+E) = O(N^2)
  • 합 : O(T * N^2) > 가능

인트 계산

  • 거리가 될수 있는 최대값 = 32767 * 2 > 인트 가능

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
vector<pi2> v;
bool chk[110];
vector<int> adj[110];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        int N; cin >> N;
        
        v.clear();
        // 출발값
        int sty,stx;
        cin >> sty >> stx;
        v.push_back(make_pair(sty, stx));
        
        // 편의점 위치 배열
        
        for(int i=0; i<N; i++) {
            int ey, ex;
            cin >> ey >> ex;
            v.push_back(make_pair(ey, ex));
        }
        int eny, enx;
        cin >> eny >> enx;
        v.push_back(make_pair(eny, enx));
 
        
        // 인접 리스트 초기화
        for(int i=0; i<110; i++) adj[i].clear();
 
        for(int i=0; i<=N+1; i++) {
            int ey = v[i].first;
            int ex = v[i].second;
            
            for(int j=0; j<=N+1; j++) {
                if(i==j) continue;
                int ny = v[j].first;
                int nx = v[j].second;
                if(abs(ey - ny) + abs(ex - nx) <= 1000) {
                    adj[i].push_back(j);
                }
                
                
            }
 
        }
        
        // st에서부터 bfs 시작해 en도착하면 종료
        fill(chk, chk+110, 0);
        
        queue<int> q;
        q.push(0);
        chk[0] = 1;
        
        bool sw = false;
        
        while(!q.empty()) {
            int eq = q.front(); q.pop();
            if(eq == N+1) {
                cout << "happy\n";
                sw = 1;
                break;
            }
            
            for(auto x : adj[eq]) {
                if(chk[x] == 1) continue;
                q.push(x);
                chk[x] = 1;
            }
        }
        
        if(sw == false) cout << "sad\n";
        
        
        
    }
    return 0;
}
 
cs

문제유형

  • BFS - 조건
    • 특정 거리 이하의 경우에만 이동할 수 있는 경우
    • 해당 조건에 만족하는 경우만 간선에 추가한 뒤 BFS 수행

'알고리즘 > 백준' 카테고리의 다른 글

백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

+ Recent posts

티스토리툴바