글 읽기 - 살려주세요... 런타임 에러를 도저히 ..... 못잡.... 으악

js3ll72 7년 전 1

아래 코드에서 BFS알고리즘을 사용하여 풀었는데..... 왜 런타임 에러가 나는지 이해할수가 없어요.

기껏해야 2500번 검사할 뿐인데..... 하.... 살려주세요

#include <stdio.h>
int n, m;
int room[52][52];//각 방의 벽 정보
int check[52][52];//각 방의 방문 정보
int room_size[2501];
int x[2502];
int y[2502];
int front, rear;
int cost = 1;
int max;
int sum, tmp;
void queue(int x_, int y_)
{
 x[rear] = x_;
 y[rear] = y_;
 //printf("%d %d\n", x_, y_);
 rear++;
}
void BFS(int x_, int y_)
{
 queue(x_, y_);
 while (front < rear)
 {
  x_ = x[front];
  y_ = y[front];
  front++;
  check[x_][y_] = cost;
  if (y_ > 1)
  {
   if ((room[x_][y_] & 1) == 0 && check[x_][y_ - 1] == 0)//왼쪽으로 뚫려있다.
    queue(x_, y_ - 1);
  }
  if (x_ > 1)
  {
   if ((room[x_][y_] & 2) == 0 && check[x_ - 1][y_] == 0)// 위로 뚫려있다.
    queue(x_ - 1, y_);
  }
  if (y_ < n)
  {
   if ((room[x_][y_] & 4) == 0 && check[x_][y_ + 1] == 0)//오른쪽으로 뚫려있다.
    queue(x_, y_ + 1);
  }
  if (x_ < m)
  {
   if ((room[x_][y_] & 8) == 0 && check[x_ + 1][y_] == 0)//아래로 뚫려있다.
    queue(x_ + 1, y_);
  }
 }
}

int main()
{
  // 입력받기
 scanf("%d %d", &n, &m);
 for (int i = 1; i <= m; i++)
 {
  for (int j = 1; j <= n; j++)
  {
   scanf("%d", &room[i][j]);
  }
 }
    
  // 같은 방은 check[i][j]에 값은 값을 저장한다.
 for (int i = 1; i <= m; i++)
 {
  for (int j = 1; j <= n; j++)
  {
   if (check[i][j] == 0)
   {
    BFS(i, j);
    cost++;
   }
   room_size[check[i][j]]++;
  }
 }// cost-1 -> 방의 개수
 
    max = 0;
 for (int i = 1; i < cost; i++)
 {
  if (max < room_size[i])
   max = room_size[i];
 }// 가장 큰 방의 사이즈
 
    
 //전체 행렬을 조사하며, check값이 달라지면(다른 방이면)다른방으로 보고 더해준다.
    sum = 0;
 for (int i = 1; i <= m; i++)
 {
  for (int j = 1; j <= n - 1; j++)
  {
   if (check[i][j] != check[i][j + 1])
   {
    tmp = room_size[check[i][j]] + room_size[check[i][j + 1]];
    if (tmp > sum)
     sum = tmp;
   }
  }
 }
    
    for (int i = 1; i <= n; i++)
 {
  for (int j = 1; j <= m - 1; j++)
  {
   if (check[j][i] != check[j + 1][i])
   {
    tmp = room_size[check[j][i]] + room_size[check[j+1][i]];
    if (tmp > sum)
     sum = tmp;
   }
  }
 }
 printf("%d\n", cost - 1);
 printf("%d\n", max);
 printf("%d", sum);

 return 0;
}

dotorya 7년 전 1

BFS 구현에서 문제가 발생하는 것 같습니다.

BFS의 방문 체크 부분은 큐에 해당 노드가 들어갈 때 진행해야 중복으로 들어가지 않을 것 같습니다.

저렇게 하시면 같은 정점이 큐에 여러개 들어갈 수 있어, 큐의 크기가 2500을 넘을 수 있을 것 같네요.

js3ll72 7년 전 1

dotorya님 감사합니다... 와.... 어제 두시간동안 계속 봤는데 안보이던게 이제서야 보이네요..

정말 감사합니다. 이렇게 또 하나 배워가네요.

크.. 상쾌하네요.

존경합니다!! 행복한하루 되시길 바래요!!

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

문제

문제

출처

ICPC

살려주세요... 런타임 에러를 도저히 ..... 못잡.... 으악

js3ll72 7년 전 1

dotorya 7년 전 1

js3ll72 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말