백준, BOJ, 1697번 C++ [CPP]

BFS의 응용문제로

BFS라고 생각지 않지만 의외로 BFS라서 놀라는

초보인 나에게는 놀라움의 대상이었던 문제다.

 

 

 

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

 

---

 

이 문제도 내가 풀긴 풀었지만

왠지 더 잘 풀수 있을 것 같다.

 

#1 뭔가 틀린 풀이

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int dist[100001]; // 0<=  n   <= 100000

int m, n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> m >> n;
    
    queue<int> Q;
    
    fill(dist, dist+100000, -1); // 0~ 100000까지 -1
    
    
    dist[m] = 0;
    Q.push(m);
    
    while(!Q.empty()){
        int cur = Q.front();
        Q.pop();
        
        
        if(cur-1 >= 0 && dist[cur-1] < 0){
            dist[cur-1] = dist[cur] + 1;
            Q.push(cur-1);
        }
        if(cur+1 <= 100000 && dist[cur+1] < 0){
            dist[cur+1] = dist[cur] + 1;
            Q.push(cur+1);
        }
        if(cur*2 <= 100000 && dist[cur*2] < 0){
            dist[cur*2] = dist[cur] + 1;
            Q.push(cur*2);
        }
        
        if(dist[n] != -1){
            cout<<dist[n];
            break;
        }
        
    }

    
}

 

그냥 무심코 보면 맞아보인다.

하지만 입력으로 99999 100000을 넣었을 때 1이 나와야 하지만 0이 나와서 틀린다.

 

역시 경계에서 조심해야한다. 그렇다면 원인이 무엇이냐?

흠.. 분명 나는 fill로 -1을 채웠단 말이지 근데도 0이 나온다는건

 

0으로 입력을 시켰거나 fill이 작동하지 않았거나 그럴 것이다.

하지만 0으로 입력이 되는 경우는 출발점만 그렇기 때문에 그럴 일이 없다.

즉, fill 이 작동하지 않았고 0으로 초기화된 상태 그대로 있었다는 말이다.

 

그렇더라도

그리고 저 while문에 99999가 들어갔다면

99998 과 100000은 1이 되어야 하는데...?

하지만 저기에 조건이 dist[cur+1] < 0 이기에

이미 100000이 0이 되었다면 저 문장이 실행이 되지 않으므로..? 0 그대로 남아있는 것이다.

 

fill을 잘못배웠다.

다시 정리하자면

 

 

100001크기의 배열 모두를 -1로 채우고 싶었다면

dist, dist+100001을 했어야 했다.

**마지막 경계값이 바뀌는지 잘 생각해보자

 

#2 맞는 풀이

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int dist[100001]; // 0<=  n   <= 100000

int m, n;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> m >> n;
    
    queue<int> Q;
    
    fill(dist, dist+100001, -1); // 0~ 100000까지 -1
    
    
    dist[m] = 0;
    Q.push(m);
    
    while(!Q.empty()){
        int cur = Q.front();
        Q.pop();
        
        
        if(cur-1 >= 0 && dist[cur-1] < 0){
            dist[cur-1] = dist[cur] + 1;
            Q.push(cur-1);
        }
        if(cur+1 <= 100000 && dist[cur+1] < 0){
            dist[cur+1] = dist[cur] + 1;
            Q.push(cur+1);
        }
        if(cur*2 <= 100000 && dist[cur*2] < 0){
            dist[cur*2] = dist[cur] + 1;
            Q.push(cur*2);
        }
        
        if(dist[n] != -1){
            cout<<dist[n];
            break;
        }
        
    }

    
}

 

 

 

 

하지만 내 생각엔 더욱 더 깔끔한 풀이가 있다고 생각해서 찾아보았다.

 

#3 남의 풀이

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int dist[100002];
int n,k;
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  fill(dist, dist+100001,-1);
  dist[n] = 0;
  queue<int> Q;
  Q.push(n);
  while(dist[k] == -1){
    int cur = Q.front(); Q.pop();
    for(int nxt : {cur-1, cur+1, 2*cur}){
      if(nxt < 0 || nxt > 100000) continue;
      if(dist[nxt] != -1) continue;
      dist[nxt] = dist[cur]+1;
      Q.push(nxt);
    }        
  }
  cout << dist[k];
}

 

와우 깔끔하다.

 

나도 저걸 시간 안에 생각할 수 있었을까..?

많은 연습이 필요하겠지 

저거 하나하나 뜯어보자

 

while(!Q.empty()) -> while(dist[k] == -1) 

로 바꾸면 얻는 장점

굳이 break문으로 escape하지 않아도 된다.

 

 

for문 저렇게 파이썬의 list comprehension같이 이용

range based for loop라는 용어란다.

 

정말 쉽게 쓸 수 있고 반복을 피할 수 있다.

 

또한 쉽게 조건을 달아서 continue로 반복할 수 있다.

 

있다가 안보고 저런 식으로 한 번 다시 풀어봐야겠다.