문제링크 : 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 |