<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[백준 1463] 1로 만들기 (BFS)

BlockDMask 2017. 12. 13. 17:27
반응형

0. 제목

  • 백준 1463 1로 만들기 (BFS)

  • BOJ 1463 1로 만들기 (BFS)

1. 문제 설명

  • 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 입니다.
    1) X가 3으로 나누어 떨어지면, 3으로 나눈다.
    2) X가 2로 나누어 떨어지면, 2로 나눈다.
    3) X에서 1을 뺀다.

  • 정수 N이 주어졌을때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만드려고 합니다.

  • 연산을 사용하는 횟수의 최소값을 출력하면 됩니다.

  • 입력 - 첫째 줄에 1 보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어집니다.

  • 출력 - 첫째 줄에 연산을 하는 횟수의 최소 값을 출력합니다.

  • ex1) 입력 10 = 9 -> 3 -> 1
    3번, 1번, 1번 규칙
    으로 인하여 최소 횟수 3 을 출력하면 됩니다.

  • ex2) 입력 2 = 1
    2번 규칙
    으로 인하여 최소 횟수 1을 출력하면 됩니다.

2. 풀이 과정

  • 자료구조 Queue를 이용한, BFS(Breadth First Search)로 풀었습니다.

  • queue container 에  pair class를 집어 넣어
    front 값은 숫자를 가리키도록.
    second는 해당 숫자에 도달 할때 까지의 연산의 횟수를 기록하도록 하였습니다.

  • 또한, bool 타입의 visited 배열을 선언하여 한번 방문했던 숫자는 탐색하지 않도록 하였습니다.

  • 주어진 규칙 세가지를 이용하여 bfs로 모든 경우를 탐색합니다.
    1) X가 3으로 나누어 떨어지면, 3으로 나눈다.
    2) X가 2로 나누어 떨어지면, 2로 나눈다.
    3) X에서 1을 뺀다.

  • 하지만, 이번 문제에서는 탐색 했을때의 최소 값 이므로 BFS로 탐색시에 가장 먼저 1에 도착하는 경우가 최소 입니다.
    또한, 방문 했던 지점을 표시하여 한번만 방문 하도록 하였습니다. 
    나중에 방문을 한다는 것은 그만큼 count가 늘어난 후에 방문을 한다는 뜻이기 때문입니다.


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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//https://www.acmicpc.net/problem/1463
//BOJ_1463_one
 
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
 
class makeOne{
private:
    int n;  //n
    bool visited[1000001];  //방문 했는지 확인.
    queue<pair<intint> > q; //pair의 first는 숫자를 뜻하고 second는 그 숫자에 도달할때의 횟수 입니다.
    int result;
public:
    void setNum(){
        cin >> n;
        result = 0;
        memset(visited, falsesizeof(bool* (n+1));
    }
    
    //BFS
    void solution(){
        int idx = n;
        int cnt = 0;
        q.push(pair<intint>(idx, cnt));   //맨 첫 값
        
        while(1){
            if(idx == 1){   //BFS중 가장 빨리 도착한 것이 가장 짧은 거리 이기 때문
                result = q.front().second;
                break;
            }
            
            //방문을 확인한 이유는 bfs 특성상 나중에 해당 idx에 방문한 것은 그만큼 cnt가 높기 때문에 굳이 방문할 필요가 없다.
            if(!visited[idx-1]){    //1 뺴기
                q.push(pair<intint>(idx-1, cnt+1));
            }
            if(!visited[idx/2&& idx%2==0){    //2로 나누어 떨어지는 경우
                q.push(pair<intint>(idx/2, cnt+1));
            }
            if(!visited[idx/3&& idx%3==0) {   //3로 나누어 떨어지는 경우
                q.push(pair<intint>(idx/3, cnt+1));
            }
            
            visited[idx] = true;    //방문 확인.
            q.pop();    //queue의 맨 앞에 값을 빼준다. (먼저 pop 하는 이유는 n,0 이 먼저 들어와서 검사를 했기 때문)
            idx = q.front().first;  //맨 앞 값이 된 값을 저장.
            cnt = q.front().second;
        }
    }
    
    void printMin(){
        cout << result;
    }
};
 
int main(void){
    makeOne one;
    one.setNum();
    one.solution();
    one.printMin();
    return 0;
}
 
cs


4. 인증



(**만약 visited 를 사용하지 않고 방문한 곳을 또 방문 하도록 코드를 작성한다면 상당히 비효율 적 입니다.)

(시간과 메모리를 몇십배로 잡아 먹게 됩니다. 아래 결과는 위 코드에서 visited를 제외 했을때의 결과 입니다.)


<문제 출처>

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


감사합니다.

도움이 되었다면 하트 한번 부탁드리겠습니다!

반응형