글 읽기 - 4963 섬의 갯수

khj878 7년 전 0

해당 arr(지도)에 값 출력도 확인해보고 check배열의 값도 다 확인해봤는데요

알고리즘 상으로는 어떤부분이 틀렸는지 계속 보고 게시판에 있는 소스들을 봤는데도

어느부분이 어떻게 틀렸는지 감이 잘 안오네요

사소한 실수 같아서 더욱 그런거 같구요..

testcase 마지막 경우에 빼고 잘 동작하구요

마지막 경우에 9가아니라 7이 나오는데

이 부분 어떻게 해결해야 하는지 고수님들 조언 부탁드리겠습니다..

#include <stdio.h>
#include <iostream>
using namespace std;

int queue[200005][2];
int front, rear;

int arr[55][55];
int check[55][55];

int x, y;
int dx[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
int dy[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };

void BFS();

void init()
{
	for (int i = 0; i <= y; i++)
		for (int j = 0; j <= x; j++)
			check[i][j] = 0;
	for (int i = 0; i <= y; i++)
		for (int j = 0; j <= x; j++)
			arr[i][j] = 0;
}

int main()
{
	scanf("%d %d ", &x, &y);
	while (x != 0 && y != 0) {
		int cnt = 0;
		for (int i = 1; i <= y; i++)
			for (int j = 1; j <= x; j++)
				scanf("%d ", &arr[i][j]);


		for (int i = 1; i <= y; i++) {
			for (int j = 1; j <= x; j++) {
				if (check[i][j] == 0 && arr[i][j] == 1) {
					cnt++;
					rear = 0;
					front = 0;
					queue[rear][0] = i;
					queue[rear][1] = j;
					check[i][j] = 1;
					rear++;
					BFS();
					/*
					for (int i = 1; i <= 5; i++) {
						for (int j = 1; j <= 5; j++)
							printf("%d ", check[i][j]);
						printf("\n");
					}
					printf("\n");
					*/
				}
			}
		}
		cout << cnt << endl;

		init();
		scanf("%d %d ", &x, &y);
	}

	return 0;
}


void BFS()
{
	int x, y;

	while (front <= rear) {
		x = queue[front][0];
		y = queue[front][1];
		front++;

		//8방향 검사
		for (int i = 0; i < 8; i++) {
			if (arr[x - dx[i]][y - dy[i]] == 1 && check[x - dx[i]][y - dy[i]] == 0) {
				check[x - dx[i]][y - dy[i]] = 1;
				queue[rear][0] = x - dx[i];
				queue[rear][1] = y - dy[i];
				rear++;
			}
		}
	}
}

ntopia 7년 전 1

이거 때문에 답이 틀리는지는 확실치는 않지만

bfs안에서 다음좌표로 뻗어나갈때 배열범위를 벗어날 수 있습니다.

큐에 넣기전에 범위체크를 한번 해보면 좋을 것 같네요.

etaehyun4 7년 전 1

while (front < rear) 로 바꾸셔야 합니다. ntopia 님처럼 다음엔 범위체크해주시고 그리고 위 소스에서 x, y를 지역변수로도 쓰고 전역변수로도 쓰는 것도 위험하니 조심해주세요.

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

문제

문제

출처

ICPC

4963 섬의 갯수

khj878 7년 전 0

ntopia 7년 전 1

etaehyun4 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말