글 읽기 - 런타임 에러 질문드립니다.

chainpark 6년 전 0

코드는 다음과 같이 짰습니다.

1. 2차원 배열 int a[x][y]에 입력을 받음 동시에 큐에 1이 들어가는 index i,j 를 push

2. bool visit[x][y]에 해당 index x y의 방문 여부 표기

3. BFS로 탐색시작.
3-1) 큐의 front의 좌표를 가져오고, visit에서 방문 표시

3-2) 상하좌우의 조건을 토대로 탐색 결정(방문한 적 없고 해당 위치에 배추가 심어져있을 경우(1일경우) 방문하고, 해당 위치를 0으로 초기화)

3-3) 상하좌우 탐색이 끝난 큐의 front pop

3-4) 3-1부터 반복

4. 전체 배열 내의 1의 갯수를 집계, ans로 출력

BFS를 잘 못 설정한 것일까요? 테스트 케이스의 경우는 맞아떨어졌습니다.

저렇게한게 각 덩어리의 시작점은 1로 남지만 각 덩어리의 나머지는 다 0으로 초기화되서 카운트 하기 쉽고

visit의 여부를 조건으로 탐색을 하고 visit의 값에도 변화를 주기 때문에 원형 데이터의 요소가 유지될 것이라는 생각에 저렇게 코드를 짰습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int a[51][51] = { 0 };
bool visit[51][51] = { false };
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,1,-1 };
vector <pair<int, int>>point;
queue <pair<int, int>>q;
int n, m,k;

void BFS()
{	
	while(!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		visit[x][y] = true;
		int i = 0;
		for (i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (a[nx][ny] == 1&&visit[nx][ny]==false)
			{
				visit[nx][ny] = true;
				a[nx][ny] = 0;
			}
		}
		q.pop();
	}

}

int main(void)
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> m >> n >> k;
		int i, j;
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= m; j++)
			{
				a[i][j] = 0;
				visit[i][j] = false;
			}
		}
		for(int x=0;x<k;x++)
		{
			cin >> i >> j;
			a[i][j] = 1;
			q.push(pair<int, int>(i, j));
		}
		BFS();
		int ans = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (a[i][j] == 1)
				{
					ans++;
				}
			}
		}
		cout << ans << "\n";
	}
}

djm03178 6년 전 1

int nx = x + dx[i];

int ny = y + dy[i];

if (a[nx][ny] == 1&&visit[nx][ny]==false)

nx와 ny가 배열의 범위를 벗어나지 않는다는 보장이 있나요?

chainpark 6년 전 0

고맙습니다. 범위 설정을 해주니 런타임 에러는 해결됬는데 결국 답안은 틀렸네요. 반례 잘 찾아서 해결해보겠습니다. 감사합니다

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