[C] 1697: 숨바꼭질

 사실 이 문제가 BFS 관련 문제라는 것을 빨리 깨달았다면 구현은 생각보다 쉽게 할 수 있었을 것이다.

그냥 어떻게 풀지 모르겠어서 각 경우의 수를 나누어 구해보고 있었는데 5에서 시작해 17로 가기 위한 경우를 그리던 중 가지가 뻗어지는 tree형태인 것을 확인할 수 있었다. 그리고 몇 초만에 갔는지 확인해야하므로 BFS 관련 문제인 것을 파악했다. 모르겠으면 무식하게 좀 해봐야겠다. 

 특히 이 문제 같은 경우는 갈 수 있는 방법이 3가지이므로 가지가 3개인 tree인 것을 알 수 있다.

 

 그리고 2차원 배열을 구현할 때 각 index를 써주는 것이 귀찮아서 그냥 처음에 int *ret0=&queue[front][0];로 선언하였더니 코드가 더 깔끔하고 읽기 쉽게 느껴졌다.

 또 queue[1000000][1] 부분에는 queue[rear][1]=queue[front][1]+1;로 구현하여 몇 초만에 갔는지를 queue 배열 하나만으로 표현하였고 dec==1이 되면 while문을 종료하도록 코드를 구현하였다. dec=nx==end?1:dec;

 

 깨달은 점!

2차원 배열을 구현할 때  포인터를 이용해주면 더욱 쉽다

일단 좀 경우의 수를 해보고 그 다음에 코드 작성해보자!

 

#include <stdio.h>
#include <math.h>

int queue[1000000][2]; //0: 값 1:몇초 지났나
int visit[100001];


void bfs(int end)
{
  int front=1,rear=2;
  int dec=0;
  
  while(dec==0)
    {      
      int *ret0=&queue[front][0];
      int *ret1=&queue[front][1];
      int nx=*ret0+1; // 1 증가
      if(nx<=100000 && visit[nx]==0) //범위를 안벗어나고 안지나간곳
      {
        visit[nx]=1;
        queue[rear][0]=nx;
        queue[rear][1]=*ret1+1;
        dec=nx==end?1:dec;
        rear++;
      }
      nx=*ret0-1; //1 감소
      if(nx>=0 && visit[nx]==0) //범위를 안벗어나고 안지나간곳
      {
        visit[nx]=1;
        queue[rear][0]=nx;
        queue[rear][1]=*ret1+1;
        dec=nx==end?1:dec;
        rear++;        
      }  

      nx=(*ret0)*2; //순간이동
      if(nx<=100000 && visit[nx]==0) //범위를 안벗어나고 안지나간곳
      {
        visit[nx]=1;
        queue[rear][0]=nx;
        queue[rear][1]=*ret1+1;
        dec=nx==end?1:dec;
        rear++;
      }

      front++;      
      
    }
  printf("%d",queue[rear-1][1]);
}

int main(void)
  {
    int start,end;
    scanf("%d %d",&start,&end);
    visit[start]=1;
    queue[1][0]=start;
    queue[1][1]=0;
    if(start==end)
    {
      printf("0");
      return 0;
    }
    bfs(end);
    
  }