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

아이디어

  • BFS로 채널을 누르고, 위아래로 누를때 원하는 채널로 이동하는 최소의 값
  • 버튼 누르는건 어떻게?
    • 1~6번째만, 해당 자리수의 숫자 큐에 넣음
    • 에시 : 2번쨰 누르는 경우엔, 10~99까지
    • 고장난 버튼 : 각 자리에서 고장난 버튼 확인
      • 이떄 BFS이므로 중복체크 해주기

시간복잡도 계산

  • 큐에 최대 들어갈수 있는수(노드) : 5e5
  • 큐에 들어가는 노드에서, 고장난 버튼 확인 : 10
  • 최대 움직일수 있는 수(간선) : 5e5
  • BFS 시간복잡도 : O(V*10+E) : 5e6 + 5e5 = 5.5e6

인트 계산

  • 누르는 횟수 : 최대 5e5

코드

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
91
92
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
vector<int> f;
bool chk[1000010];
//bool chk[10000];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int target; cin >> target;
    
    // 중복체크 초기화
//    fill(chk, chk+500010, false);
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int a; cin >> a; f.push_back(a);
    }
    
    queue<int> q;
    q.push(100);
    chk[100] = 1;
    int cnt=0;
    while(!q.empty()) {
        int qsize = q.size();
        while(qsize--) {
            int eq = q.front(); q.pop();
            
            if(eq == target) {
                cout << cnt << '\n';
                return 0;
            }
            
            // 더하고
            if(eq+1 <=500000) {
                if(chk[eq+1] == false) {
                    chk[eq+1] = 1;
                    q.push(eq+1);
                }
            }
            
            // 빼기
            if(eq-1 >=0) {
                if(chk[eq-1] == false) {
                    chk[eq-1] = 1;
                    q.push(eq-1);
                }
            }
            
            
            
        }
        
        if(cnt<6) {
            int st = pow(10,cnt);
            if(st==1) st = 0;
            int en = pow(10,cnt+1)-1;
            
            for(int i=st; i<=en; i++) {
                if(chk[i]) continue;
                bool sw = false;
                // 각 자리수에서 금지된 숫자 있는지 확인
                for(int j=0; j<=cnt; j++) {
                    // 각자리숫자
                    int num = (int)(i/pow(10,j)) % 10;
                    if(find(f.begin(), f.end(), num) != f.end()) {
                        sw = true;
                        break;
                    }
                    
                }
                
                // 금지된 숫자에 걸리는 것이 없다면 큐에 넣기
                if(sw == false){
                    chk[i] = 1;
                    q.push(i);
                }
            }
        }
        
        cnt++;
    }
    
    return 0;
}
 
cs

문제유형

  • BFS - 최소 횟수

비슷한 문제

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

백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1946 신입 사원  (0) 2021.02.15

+ Recent posts

티스토리툴바