#1697 숨바꼭질

문제는 위와 같다(실버1). 문제를 처음 봤을때는 이게 왜 bfs문제 이지? 생각했다. 백준 수업을 듣고 알게되었다.

 

 

BFS를 이용해 풀 수 있는 문제는 다음의 조건을 충족한다

1. 최소 비용 문제여야 한다

2. 간선의 가중치가 1 이어야 한다.

3. 정점과 간선의 개수가 문제의 조건에 맞추어 해결할 수 있을 정도로 적어야 한다.

++ 간선의 가중치가 문제에서 구하라고 하는 최소 비용과 의미가 일치해야한다.

(즉, 최단거리 문제라면 가중치는 거리를 의미해야하고, 최단시간 문제라면 가중치는 시간을 의미 해야 한다.)

 

 

#include <iostream>
#include <queue>
#define MAX 100000
using namespace std;

int n,k;
int visited[100001];
int dist[100001];
queue<int> q;

void bfs(int x){
  visited[x]=1;
  dist[x]=0;
  q.push(x);
  while(!q.empty()){
    int now=q.front();
    q.pop();
    if(now-1>=0&&visited[now-1]==0){
      q.push(now-1);
      visited[now-1]=1;
      dist[now-1]=dist[now]+1;
    }
    if(now+1<=MAX&&visited[now+1]==0){
      q.push(now+1);
      visited[now+1]=1;
      dist[now+1]=dist[now]+1;
    }
    if(2*now<=MAX&&visited[2*now]==0){
      q.push(2*now);
      visited[2*now]=1;
      dist[2*now]=dist[now]+1;
    }
  }
}

int main() {
  freopen("input.txt", "r", stdin);
  cin>>n>>k;

  bfs(n);
  cout<<dist[k]<<'\n';
}

코드는 위와같다. 처음에는 그래프를 어떻게 구성할까?를 고민했었다. 이런 고민을 한다는게 내가 문제를 많이 풀어보지 못해서 이런 유형을 많이 접해보지 못한 이유인것 같다. 이 문제는 수빈이의 위치가 정점이 되고, 걷기와 순간이동이 간선이 되는 문제이다. 꼭 그래프를 구성하지 않아도 풀 수 있다!

 

★ 배운 것

1. 그래프를 꼭 구성해야하는건 아니다.

여태 껏 푼 문제들은 map[max][max] 등의 배열에 1을 대입한다던가 하는 식으로 그래프를 구성 했었다. 근데 이문제는 그러지 않고 푸는 문제였다. 유연한 사고가 필요한...