[C++] BOJ 1697 / BFS (fill, range based for 사용)

문제 분석

BFS 문제는 2차원 배열로 주어지는것이 흔한데, 이 문제는 특이하게 1차원인데다가, "상 하" 이동 없이 "좌 우"로만 이동하기 때문에 BFS를 떠올리는 것이 힘들었다.

 

해결 방법

1차원 배열에서 BFS를 돌리면서, 동생의 위치와 인덱스가 겹칠 때의 distance 값을 출력한 후 종료하면 된다.

 

코드

#include <iostream>
#include <queue>

using namespace std;
int dist[100001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    int n,k;
    fill(dist, dist+100001, -1);
    cin >> n >> k;
    if(n == k) {
        cout << 0;
         return 0;
    }
    q.push(n);
    while(!q.empty()){
        int cur = q.front(); 
        q.pop();
        for(int nx : {cur-1, cur+1, cur*2}) {
            if(nx < 0 || nx >= 100001) continue;
            if(dist[nx] != -1) continue;
            dist[nx] = dist[cur] + 1;
            if(nx == k) {
                cout << dist[nx]+1;
                return 0;
            }
            q.push(nx);
        }
    }
}

 

- fill 함수

<algorithm> 에 정의되어 있다.

void fill(ForwardIterator first, ForwardIterator last, const T& val);

범위 내 (first 부터 last 전 까지) 원소들에 val 을 대입한다.

• first, last
  • 값을 대입할 원소들의 시작과 끝을 가리키는 반복자들.
  • first가 가리키는 원소는 포함되지만, last가 가르키는 원소는 포함되지 않는다.
• val 
  • 어떤 값을 대입할 지

 

- range base for, 범위기반 for 반복문

기존의 for 반복문과 달리, 시작과 끝점을 알려주지 않아도 알아서 처음부터 끝까지 순회를 해주는 반복문이다.

 

for (데이터 타입 elem : 데이터 리스트) { ... }

주의할 점으로는 elem 값을 변경해도, 리스트의 값이 변하지는 않는다.

( range base for문 내부에서는 배열의 요소를 변경할 수 없다)

 

데이터 리스트에는 선언된 배열, 벡터, 리스트 등을 넣어도 되고, 위 문제풀이 코드에서 했듯이 직접 선언해도 된다.

 

참고 링크

• fill 함수
  • https://modoocode.com/267
• range based for
  • https://blockdmask.tistory.com/319