gaelim   2년 전

백준님 강의를 듣고, 어느정도 개념을 이해하고 코딩을 했는데.... 예제는 잘 돌아갔습니다.
그런데 시간초과가 떠서 희안하더라구요, 코딩 답을 보고 비교를 해보았는데, 개념적으로 비슷해서 알고리즘 문제가 아닌거같다고 생각하고있습니다. 다른점은 제가 배열을 1차원으로 선언하여 m, n을 이용하여 row column을 새로 계산하여 이동하였구요...

어떤 것이 문제일까요. scanf 또한 %1d 양식으로 입력받았습니다... 도중에 2차원을 1차원을 축소하는데 헷갈려서 실수한것일까요??....

아니면 scanf의 실수일까요..?


#include <cstdio>
#include <queue>

using namespace std;
int arr[200];
int dist[200];
int dx[4]= {0, 0, -1, 1};
int dy[4]= {-1, 1, 0, 0};

int main(){

  int m, n;
  scanf("%d %d", &m, &n);

  for(int i=0; i<n; i++){
    for (int j=0; j<m; j++){
      scanf("%1d", &arr[i*m+j]);
      dist[i*m+j]=-1;
    }
  }

  queue<int> que;
  queue<int> postque;

  que.push(0);
  dist[0]=0;
  while(!que.empty()){
    int now=que.front();
    que.pop();
    for (int i=0;i<4; i++){
      int nx=now/m+dx[i];
      int ny=now%m+dy[i];
      if (nx>=0 && nx<n && ny >=0 && ny <m){
        if (dist[nx*m+ny]==-1){
          if (!arr[nx*m+ny]){
            dist[nx*m+ny]= dist[now];
            que.push(nx*m+ny);
          }else{
            dist[nx*m+ny] = dist[now]+1;
            postque.push(nx*m+ny);
          }
        }
      }
    }
    if(que.empty()){
      while(!postque.empty()){
        que.push(postque.front());
        postque.pop();

      }
    }
  }

  printf("%d\n", dist[n*m-1]);
  return 0;
}

startlink   2년 전

가로 세로 범위 변수 헷갈리지 않았나 확인해보세요

gaelim   2년 전

가로 세로 범위 변수 헷갈릴까봐, 코드의 가독성을 높이기 위해 다음과 같이 수정했고, 한동안 보고있는데 어떤것이 잘못되었는지 잘모르겠습니다.. 제생각엔 다른점은 1차원 배열로 푼것 밖에 없는것같은데 여전히 시간초과가 뜹니다.  또는 제가 scanf "1d" 의 동작원리를 잘 모르는것일수도 있겠습니다만...

#include <cstdio>
#include <queue>

using namespace std;
int arr[200], dist[200];
int dx[4]= {0, 0, -1, 1};
int dy[4]= {-1, 1, 0, 0};

int main(){

  int m, n;
  scanf("%d %d", &m, &n);

  for(int x=0; x<n; x++){
    for (int y=0; y<m; y++){
      scanf("%1d", &arr[x*m+y]);
      dist[x*m+y]=-1;
    }
  }

  queue<int> que;
  queue<int> postque;

  que.push(0);
  dist[0]=0;
  while(!que.empty()){
    int now=que.front();
    que.pop();
    for (int i=0;i<4; i++){
      int x=now/m, y=now%m;
      int nx=x+dx[i], ny=y+dy[i];

      if (nx>=0 && nx<n && ny >=0 && ny <m){
        if (dist[nx*m+ny]==-1){
          if (!arr[nx*m+ny]){
            dist[nx*m+ny]= dist[now];
            que.push(nx*m+ny);
          }else{
            dist[nx*m+ny] = dist[now]+1;
            postque.push(nx*m+ny);
          }
        }
      }
    }
    if(que.empty()){
      while(!postque.empty()){
        que.push(postque.front());
        postque.pop();
      }
    }
  }
  printf("%d\n", dist[n*m-1]);
  return 0;
}

댓글을 작성하려면 로그인해야 합니다.