Silver III 난이도 문제를 C++로 풀이한 내용입니다. 정수 N이 주어졌을 때, 연산을 최소 횟수로 사용하여 1로 만드는 문제입니다.

백준 1463: 1로 만들기

Silver III 난이도 문제를 C++로 풀이한 내용입니다. 정수 N이 주어졌을 때, 연산을 최소 횟수로 사용하여 1로 만드는 문제입니다.

문제 소개

문제 번호: 1463
문제명: 1로 만들기
난이도: Silver III
사용 언어: C++
실행 시간: 0 ms
메모리: 5928 KB
문제 요약: 주어진 정수 N을 1로 만들기 위해 다음 세 가지 연산 중 가능한 연산을 선택하여 최소 횟수로 1을 만드는 방법을 찾습니다.
1. X가 3으로 나누어 떨어지면 3으로 나눈다.
2. X가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.

접근 방법

이 문제는 주어진 정수 N에서 시작하여 목표값인 1에 도달하기까지의 최소 연산 횟수를 찾는 문제입니다. 이러한 "최단 경로" 또는 "최소 횟수"를 찾는 문제는 그래프 탐색 알고리즘, 특히 **너비 우선 탐색(BFS)**을 떠올리게 합니다.

각 정수를 노드로 생각하고, 가능한 연산을 엣지로 간주하는 그래프를 상상할 수 있습니다. 예를 들어, 숫자 10에서 시작한다면 다음과 같은 엣지들이 존재합니다:

10 -> 9 (1 빼기)
10 -> 5 (2로 나누기)

BFS는 시작 노드에서 가장 가까운(즉, 가장 적은 엣지를 거친) 노드를 순서대로 탐색하므로, N에서 1로 가는 최단 경로를 찾는 데 적합합니다.

따라서, N을 시작점으로 하여 BFS를 수행하고, 각 숫자에 도달하기까지의 연산 횟수를 기록합니다. 처음으로 1에 도달했을 때의 연산 횟수가 바로 최소 연산 횟수가 됩니다.

풀이 과정

데이터 구조 선택:
- 탐색 과정에서 방문한 노드(정수)와 해당 노드에 도달하기까지의 최소 연산 횟수를 저장하기 위해 std::vector<int> visited(N + 1, -1)를 사용합니다. visited[i]는 정수 i에 도달하기까지의 최소 연산 횟수를 저장하며, -1은 아직 방문하지 않았음을 의미합니다.
- BFS를 위한 큐(std::queue<int> q)를 사용합니다.
초기화:
- 시작 정수 N을 큐에 넣습니다.
- visited[N]를 0으로 설정하여, 시작점 N은 0번의 연산으로 도달했다고 표시합니다.
BFS 탐색:
- 큐가 비어있지 않은 동안 반복합니다.
- 큐의 front에 있는 현재 정수 x를 꺼냅니다.
- 만약 x가 1이라면, 우리는 목표에 도달한 것이므로 visited[x] (즉, visited[1])에 저장된 연산 횟수를 출력하고 프로그램을 종료합니다.
자식 노드 탐색 및 큐에 추가:
- x가 1이 아니라면, 가능한 세 가지 연산을 수행하여 얻을 수 있는 다음 정수(자식 노드)들을 확인합니다.
- x - 1: 만약 x - 1이 1 이상이고 아직 방문하지 않았다면 (visited[x - 1] == -1), visited[x - 1]을 visited[x] + 1로 업데이트하고 x - 1을 큐에 추가합니다.
- x / 2: 만약 x가 2로 나누어 떨어지고 아직 방문하지 않았다면 (visited[x / 2] == -1), visited[x / 2]를 visited[x] + 1로 업데이트하고 x / 2를 큐에 추가합니다.
- x / 3: 만약 x가 3으로 나누어 떨어지고 아직 방문하지 않았다면 (visited[x / 3] == -1), visited[x / 3]를 visited[x] + 1로 업데이트하고 x / 3을 큐에 추가합니다.
BFS 특성: BFS는 레벨별로 탐색하기 때문에, 어떤 숫자에 처음 도달했을 때의 연산 횟수가 바로 해당 숫자에 도달할 수 있는 최소 연산 횟수가 됩니다. 따라서 중복 방문을 방지하고 최단 경로를 보장합니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); // 표준 입출력 속도 향상
    cin.tie(NULL); // cin과 cout의 묶음을 해제하여 입력 속도 향상

    int N; // 시작 정수 N
    cin >> N;

    // visited 벡터: 인덱스는 현재 수, 값은 해당 수에 도달하기까지의 연산 횟수
    // 초기값 -1은 아직 방문하지 않았음을 의미
    vector<int> visited(N + 1, -1); 
    queue<int> q; // BFS 탐색을 위한 큐

    q.push(N); // 주어진 시작 정수 N을 큐에 삽입
    visited[N] = 0; // 시작 정수는 연산 횟수 0으로 시작

    while (!q.empty()) { // 큐가 비어있지 않은 동안 BFS 수행
        int x = q.front(); // 큐의 가장 앞 요소를 꺼냄 (현재 정수)
        q.pop(); // 큐에서 해당 요소를 제거

        if (x == 1) { // 목표값인 1에 도달했으면
            cout << visited[x]; // 1에 도달하기까지의 연산 횟수 출력
            return 0; // 프로그램 종료
        }
        
        // 아직 1이 아니면, 가능한 연산들을 통해 다음 상태(정수)를 탐색
        
        // 1. x - 1 연산: 1을 빼는 경우
        //    - 결과가 1 이상이고, 아직 방문하지 않은 경우 (-1)
        if (x - 1 >= 1 && visited[x - 1] == -1) {
            visited[x - 1] = visited[x] + 1; // 연산 횟수 1 증가하여 기록
            q.push(x - 1); // 탐색할 큐에 추가
        }

        // 2. x / 2 연산: 2로 나누는 경우
        //    - x가 2로 나누어 떨어지고, 결과가 아직 방문하지 않은 경우
        if (x % 2 == 0 && visited[x / 2] == -1) {
            visited[x / 2] = visited[x] + 1; // 연산 횟수 1 증가하여 기록
            q.push(x / 2); // 탐색할 큐에 추가
        }

        // 3. x / 3 연산: 3으로 나누는 경우
        //    - x가 3으로 나누어 떨어지고, 결과가 아직 방문하지 않은 경우
        if (x % 3 == 0 && visited[x / 3] == -1) {
            visited[x / 3] = visited[x] + 1; // 연산 횟수 1 증가하여 기록
            q.push(x / 3); // 탐색할 큐에 추가
        }
        
        // BFS의 특성상, 위의 if문들이 끝나는 이유는 다음과 같습니다.
        // "상태 전이 함수만 정확히 정의하면, 나머지는 자료구조와 BFS 모델이 알아서 최적해를 만들어준다."
        // → 최단경로 보장
        // → 레벨 순회 (가까운 노드부터 탐색)
        // → 중복은 패스 (visited 배열 활용)
        // → 종료 조건 관리 (x == 1)
    }
    
    return 0; // 루프가 종료되면 (이론상 발생하지 않음) 0 반환
}

복잡도 분석

시간 복잡도: O(N)
BFS는 각 노드를 최대 한 번 방문하며, 각 노드에서 수행하는 연산(3가지 연산 확인 및 큐 삽입/삭제)은 상수 시간이 걸립니다. 따라서, 탐색하는 정수의 최대값 N에 비례하는 시간 복잡도를 가집니다.
공간 복잡도: O(N)
visited 벡터는 N+1 크기를 가지며, 큐는 최악의 경우 N개의 요소를 저장할 수 있습니다. 따라서 공간 복잡도는 N에 비례합니다.

배운 점

이 문제는 BFS의 기본적인 활용 방법을 다시 한번 상기시켜주는 좋은 예시였습니다. 특히 다음과 같은 점들을 배울 수 있습니다.

문제의 상태와 연산을 그래프로 모델링하는 능력: 정수 N을 노드, 가능한 연산을 엣지로 생각함으로써 BFS를 적용할 수 있었습니다.
최단 경로 문제에 BFS 적용: 최소 횟수를 구하는 문제가 주어졌을 때 BFS가 강력한 도구임을 인지하게 되었습니다.
방문 배열의 중요성: visited 배열을 사용하여 중복 탐색을 방지하고, 각 상태에 도달하는 최소 연산 횟수를 효율적으로 기록할 수 있었습니다.
상태 전이 함수 정의의 중요성: 문제 해결을 위한 핵심 연산(상태 전이)만 정확하게 정의하면, BFS 알고리즘 자체가 최적의 경로를 찾아준다는 것을 이해했습니다.