글 읽기 - 메모리초과 때문에 질문드립니다

njchung99 6년 전 0

각각 뭉쳐있는것마다 dfs로 number를 나누어준뒤에 bfs로 num가 다를경우에 그값을 받아서 그중 최소값을 받도록 하였는데 메모리 초과가 떠서 질문드립니다.

 #include<cstdio>
 #include<algorithm>
 #include<queue>
 #include<cstring>
 using namespace std;
 int n, map[110][110],visit[110][110],map_num,cnt,visit1[110][110],dap=10000000;
 int l[4] = { 0,0,-1,1 };
 int r[4] = { 1,-1,0,0 };
 void dfs(int x, int y)
 {
  visit[x][y] = map_num;
  for (int i = 0; i < 4; i++)
  {
   if (0<=x + l[i]&&x+l[i]<n&&n> y + r[i]&&y+r[i]>=0)
   {
    if (map[x + l[i]][y + r[i]] && !visit[x + l[i]][y + r[i]])
     dfs(x + l[i], y + r[i]);
   }
  }
 }
 int main()
 {
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
   for (int y = 0; y < n; y++)
   {
    scanf("%d", &map[i][y]);
   }
  }
  for (int i = 0; i < n; i++)
  {
   for (int y = 0; y < n; y++)
   {
    if (map[i][y] && !visit[i][y])
    { 
     map_num++;
     dfs(i, y);
    }
   }
  }
  for (int i = 0; i < n; i++)
  {
   for (int y = 0; y < n; y++)
   {
    if (map[i][y])
    {
     int check = 0;
     for (int z = 0; z < 4; z++)
     {
      if (i + l[z]>=0&&i+l[z]<n&& n>y + r[z]&&y+r[z]>=0)
      {
       if (!map[i + l[z]][y + r[z]])
        check++;
      }
     }
     if (check)
     {
      memset(visit1, 0, sizeof(visit1));
      int flag = 1; int num = visit[i][y], cnt = 0;
      queue<pair<int, int>> qu;
      for (int z = 0; z < 4; z++)
      {
       if (i + l[z]>=0&&i+l[z]<n&& n>y + r[z]&&0<=y+r[z])
       {
        if (!map[i + l[z]][y + r[z]])
         qu.push({ i + l[z],y + r[z] });
       }
      }
      while (1)
      {
       cnt++;
       if (!qu.size())break;
       if (!flag)break;
       int ps = qu.size();
       while (ps--)
       {
        int nx = qu.front().first;
        int ny = qu.front().second;
        visit1[nx][ny] = 1;
        qu.pop();
        for (int z = 0; z < 4; z++)
        {
         if (0 <= nx + l[z] && nx + l[z]<n&&0<= ny + r[z]&&ny+r[z]<n)
         {
          if (!visit1[nx + l[z]][ny + r[z]]&& visit[nx + l[z]][ny + r[z]] != num)
           qu.push({ nx + l[z], ny + r[z] });
          if (visit[nx + l[z]][ny + r[z]] > 0 && visit[nx + l[z]][ny + r[z]] != num)
          {
           dap = min(cnt, dap);
           flag = 0;
          }
         }
        }
       }
      }
     }
    }
   }
  }
  printf("%d", dap);
 }

djm03178 6년 전 4

BFS에서는 큐에서 꺼낼 때 방문 표시를 하는 게 아니라, 큐에 넣을 때 해야 중복 방문이 일어나지 않습니다.

이 문장을 어디다가 적어놓고 복붙해야할 것 같습니다.

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

문제

문제

출처

ICPC

메모리초과 때문에 질문드립니다

njchung99 6년 전 0

djm03178 6년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말