[C] 14940: 쉬운 최단거리

전형적인 BFS 문제로 각 목표지점까지의 거리를 출력하면 된다.

이때 각 거리를 저장하는 배열은 visit를 이용하였고 queue를 이용하여 bfs를 구현하였다. 

주의해야할 점은

1.거리를 계산하기 위해 queue[2][] 부분을 거리를 위한 공간으로 할당하였고  queue[2][rear]=queue[2][front]+1;  를 통해 거리를 구할 수 있다.

2. 2가 있던 자리를 visit 배열에서 1로 할당했기 때문에 마지막에 출력하는 부분에서 0이 출력하도록 바꿔야한다.

 

이건 꼭 좀 잘하자!

맨날 풀었던 문제인데 bfs 구현하는데 이상한 곳에서 시간이 걸렸다.

특히 이번에는 front와 rear을 모두 1로 초기화해놓고 while문 들어가는 조건을 front<rear로 했었고

queue배열의 index를 잘못 적었다. 

-> 반복문 들어가는 조건과 다차원배열 index 쓰는 걸 유의하자!!

 

#include <stdio.h>

int graph[1001][1001];
int visit[1001][1001];
int queue[3][1000001]; // 0:x좌표 1:좌표 2: 몇번째인지
int x_coordinate[4]={1,-1,0,0};
int y_coordinate[4]={0,0,1,-1};

void bfs(int y,int x)
{
  int front=1;
  int rear=2;
  
  while(front<rear )
  {
    for(int i=0;i<4;i++)
    {
        int nx=queue[0][front]+x_coordinate[i];
        int ny=queue[1][front]+y_coordinate[i];

       if(ny<1||nx<1||ny>y||nx>x) // 범위를 벗어남
          continue;
       if(visit[ny][nx]!=0 || graph[ny][nx]==0) //이미 지나감 || 원래 갈 수 없는 땅
          continue;
        queue[0][rear]=nx;
        queue[1][rear]=ny;    
        queue[2][rear]=queue[2][front]+1;  
        visit[ny][nx]=queue[2][rear];
        rear++;//queue애 추가!
    }
    front++; //queue에 있는거 하나 꺼냄
  }
}

void FindMinus(int n,int m)
{
  for(int j=1;j<=n;j++)
    {
      for(int i=1;i<=m;i++)
        {
          if(visit[j][i]==0 && graph[j][i]!=0)
            visit[j][i]=-1;
        }
    }
}
void PrintGraph(int y,int x)
{
  for(int j=1;j<=y;j++)
    {
      for(int i=1;i<=x;i++)
        {
          printf("%d ",visit[j][i]);
        }
      printf("\n");
    }
}

int main(void)
  {
    int n,m,x,y;
    scanf("%d %d",&n,&m); //n이 y, m이 x
    for(int j=1;j<=n;j++)
      {
        for(int i=1;i<=m;i++)
          {
            scanf("%d",&graph[j][i]);
            if(graph[j][i]==2)
            {
              x=i,y=j;
              visit[y][x]=1;
            }
          }
      }
    queue[0][1]=x;
    queue[1][1]=y;
    queue[2][1]=0;
    bfs(n,m); //visit 배열에 거리 얼마인지 저장(맨 처음위치 주의!)    
    FindMinus(n,m);
    visit[y][x]=0; //얘를 다시 0으로 만들어줘야함!!
    PrintGraph(n,m);
   
  }