«   2022/08   »
  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      
Archives
Today
15
Total
93,052
관리 메뉴

차근차근

[백준 1697] 숨바꼭질 본문

대학교/Algorithm

[백준 1697] 숨바꼭질

SWKo 2020. 3. 19. 02:37

0. 제목

  • 백준 1697 숨바꼭질
  • BOJ 1697 숨바꼭질
  • C++ 1697 숨바꼭질

1. 문제

https://www.acmicpc.net/problem/1697


2. 풀이

  • 완전탐색을 푸는데에 5가지 방법이 있다.
    • brute force(N중 for문)
    • 순열
    • BFS(최소를 구하는 문제)
    • 비트마스크
    • 백트래킹
  • 이 문제는 BFS를 사용하여 푼다.
  • 현재위치와 현재까지 걸린 시간을 큐에 넣고 조건을 확인해가며 push, pop을 반복한다.
  • 그렇게 반복문을 돌다가 현재위치가 동생이 있는 위치와 같아지게 되면 bfs함수는 현재까지 걸린시간을 반환한다.

3. 코드

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
#include <iostream>
#include <queue>
using namespace std;
 
const int MAX = 100001;
bool visited[MAX];
 
int bfs(int N, int K){
    queue<pair<intint>> q;
    q.push(make_pair(N, 0));
    visited[N] = true;
    
    while(!q.empty()){
        int loc = q.front().first;
        int sec = q.front().second;
        q.pop();
        
        if (loc == K) {
            return sec;
        }
        
        if(loc + 1 < MAX && !visited[loc + 1]){
            visited[loc + 1= true;
            q.push(make_pair(loc + 1, sec + 1));
        }
        if(loc - 1 >= 0 && !visited[loc - 1]){
            visited[loc - 1= true;
            q.push(make_pair(loc - 1, sec + 1));
        }
        if(loc * 2 < MAX && !visited[loc * 2]){
            visited[loc * 2= true;
            q.push(make_pair(loc * 2, sec + 1));
        }
    }
    return 100000;
}
 
int main(int argc, const char * argv[]) {
    int N, K;
    cin >> N >> K;
    
    cout << bfs(N, K) << '\n';
    
    
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1759] 암호 만들기  (0) 2020.03.22
[백준 1525] 퍼즐  (0) 2020.03.20
[백준 1697] 숨바꼭질  (0) 2020.03.19
[백준 10819] 차이를 최대로  (0) 2020.03.18
[백준 6378] 디지털 루트  (0) 2020.03.15
[백준 2225] 합분해  (0) 2020.03.14
0 Comments
댓글쓰기 폼