글 읽기 - [14502] 런타임 에러

dmstjd0112 4년 전 0

99%에서 런타임 에러가 났는데 아무리 고민해봐도 모르겠어서 질문 남깁니다.

검색도 해보고 그 간의 경험에 미루어 봐도 런타임 에러는 거의 인덱스 초과가 문제인걸 아는데도

왜 안되는지 제 눈에는 틀린 부분이 안 보이네요

코드는 대략

dfs(){}

main {

입력

3개의 벽을 세울수 있는 모든 경우의 수{

dfs로 안전지역 탐색

}

이런 구조로 되어 있고, 실력이 부족하다 보니 코드가 많이 난잡해서 죄송합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<bool>> visited;
int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int safeArea = 0;
bool flag = true;

void dfs(int startY, int startX, vector<vector<int>> &copy)
{
  safeArea++;
  visited[startY][startX] = true;
  for (int i = 0; i < 4; i++)
  {
    int nextX = startX + dx[i];
    int nextY = startY + dy[i];

    if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) //다음 지점이 연구소 범위를 넘지 않고
    {
      if (!visited[nextY][nextX]) //방문한적 없을 경우
      {
        if (copy[nextY][nextX] == 0) //다음 지점이 빈 공간인 경우
        {
          dfs(nextY, nextX, copy);
        }
        else if (copy[nextY][nextX] == 2) //다음 지점이 바이러스인 경우
        {
          flag = false;
          dfs(nextY, nextX, copy);
        }
      }
    }
  }
}

int main()
{
  scanf("%d %d", &n, &m);
  vector<vector<int>> v;
  v.assign(9, vector<int>(9, 0));
  visited.assign(9, vector<bool>(9, false));

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      scanf("%d", &v[i][j]);
    }
  }
  /////////////////////////입력 끝///////////////////////////
  int startX, startY; //dfs 시작지점
  vector<int> combination(n * m, 0);
  combination[n * m - 1] = 1;
  combination[n * m - 2] = 1;
  combination[n * m - 3] = 1;

  int maxSafeArea = 0;
  bool next = false; //벽이 바이러스나 벽 위치랑 겹칠 경우 true로 바꾸고 continue

  do
  {
    next = false;
    vector<vector<int>> copy = v;

    for (int i = 0; i < n * m; i++)
    {
      if (combination[i] == 1)
      {
        int y = i / m;
        int x = i - (y * m);
        if (copy[y][x] == 0)
        {
          copy[y][x] = 1;
        }
        else
        {
          next = true;
          break;
        }
      }
    }

    if (next)
      continue;

    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (copy[i][j] == 0)
        {
          startX = j;
          startY = i;
          goto A;
        }
      }
    }
  A:
    ////////////////////////////////////////////////////////////////////
    dfs(startY, startX, copy); //dfs를 우선 한번 돌리고
    if (!flag)                 //바이러스를 만났으면
    {
      flag = true; //flag변수를 다시 true로 바꿔준다.
      safeArea = 0;
    }

    for (int i = 0, before; i < n; i++) //컴포넌트가 2개 이상인지 확인하기 위해
    {
      for (int j = 0; j < m; j++)
      {
        if (!visited[i][j] && copy[i][j] == 0) //컴포넌트가 2개 이상이기 때문에 dfs를 다시 돌린다.
        {
          before = safeArea;
          dfs(i, j, copy);

          if (!flag)
          {
            flag = true;
            safeArea = before;
          }
        }
      }
    }

    if (flag)
    {
      maxSafeArea = (maxSafeArea < safeArea) ? safeArea : maxSafeArea;
    }

    visited.assign(9, vector<bool>(9, false));
    safeArea = 0;
    flag = true;
  } while (next_permutation(combination.begin(), combination.end()));

  printf("%d", maxSafeArea);
  return 0;
}

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

문제

문제

출처

ICPC

[14502] 런타임 에러

dmstjd0112 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말