[BaekJoon/백준] 1697번 C++

처음에 동적할당으로 문제를 풀어보려 했으나, 어려웠다. 양방향에 대한 계산이 필요했기에 어려움을 많이 겪었고

알아보니 이러한 문제에서 DP 접근은 좋지 않다는 것을 알았다.

( 관련 참고 : www.acmicpc.net/board/view/41340 )

 

풀이를 검색해보게 되었다.

 

이 문제는 BFS 알고리즘을 적용하여 풀 수 있는 문제였다.

BFS는 처음이였다. 그래서 알고리즘도 알아보고, 흐름도 이해해보게 되었다.

( 관련 참고 : 1. gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html 2. m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230944971&proxyReferer=https:%2F%2Fwww.google.com%2F )

 

위 두 블로그가 BFS에 대한 개념적인 설명이 잘 되어있었다. 감사합니다 ㅎㅎ

 

그리고 코드를 작성했다. 배열 크기를 최대로 어떻게 놓느냐가 고민거리였는데,

당시 안전하게 최대 범위인 10만에 x 2 + 1을 한 20만 + 1 범위로 설정했다. 

 

왜냐면 예를 들어 최대 값의 범위고 11이고

주어진 수가 6과 11일 때 ((6 * 2) - 1) = 12  -1 인 경우가 있기 때문이였다.

 

하지만 문제에서 최대 범위가 홀수가 아닌 짝수이기 때문에 이런 경우 배열 크기를 그냥 10만 + 1으로 해줘도 문제를 풀 수 있다.

ex) arr[100001], 인덱스 검사할 때엔 100000보다 작거나 같을 때.

이유 : (?) x 2 = 짝수

#include <iostream>
#include <vector>
#include <queue>

#define MAX 200001
using namespace std;

bool c[MAX]; // 방문한 숫자인지 체크 ( bfs에서 방문한 노드를 체크해주지 않으면 무한루프가 발생한다 )
int z[MAX]; // depth, 즉 경로길이를 계산하기 위한 배열..
int key;
int start;

// 도달할 수 계산, 이미 도달했다면 종료
// 원하는 숫자에 도달할때까지 bfs한다고 보면됨.
// 방문한 숫자(도달한 수, 이미 해당 수에 대한 경우를 다룬 후)인 경우 또다시 방문하지 않는다.
void bfs(int start) {
    
    queue<int> q;
    q.push(start);
    c[start] = true;
    
    while(!q.empty()) {
        
        int x = q.front(); q.pop();
        
        if(x != key) {
            if(x - 1 >= 0 && !c[x - 1]) { // 0 보다 아래인 경우 문제에서 다룰 필요 없고, 배열 계산에도 인덱스 에러.
                q.push(x - 1);
                c[x - 1] = true;
                z[x - 1] = z[x] + 1;
            }
            if(x + 1 <= MAX - 1 && !c[x + 1]) { // 배열 범위(최대경우)를 넘어가지 않게
                q.push(x + 1);
                c[x + 1] = true;
                z[x + 1] = z[x] + 1;
            }
            if(x * 2 <= MAX - 1 && !c[x * 2]) { // 배열 범위(최대경우)를 넘어가지 않게
                q.push(x * 2);
                c[x * 2] = true;
                z[x * 2] = z[x] + 1;
            }
        } else {
            cout << z[x];
            return;
        }
        
    }
}

int main() {

    ios::sync_with_stdio();
    cin.tie(NULL);
    
    cin >> start >> key;
    bfs(start);
}

궁금하신 분들은 위 코드에서

MAX를 12로 두고, 6 11을 입력해보고

MAX를 13로 두고, 6 11을 입력해보시면 된다.

 

두 결과가 다를 것이다.

 

이 문제에 대한 이론적 참고는 아래 블로그들이 잘 정리되어 있다!!

chanhuiseok.github.io/posts/baek-14/

velog.io/@jsi06138/백준-1697번-숨바꼭질

jaimemin.tistory.com/581

 

 

+ 2021.09.24

양방향 연결이유는, 어디서 시작할지도 모르며, 입력값이 3 2로 되어서 3 -> 2 연결했는데

탐색중 2로 시작하는 경우가 되면 끊어진 거로 볼 수 도 있고,, 등 이처럼 어디서 시작할지와 탐색 방향성과 주어진 입력에 연관된 문제이다.

(연결순서와 시작순서의 관계 등의 문제)