글 읽기 - bfs가 안돌아갑니다.. 도와주세용

sss654654 2년 전 0

결과를 visit과 board를 둘다 나타나게 하였습니다.

1 1 1 1 0 0 1
1 0 1 1 0 0 1
0 0 0 0 1 1 1
0 0 0 0 1 1 1
1 0 1 1 1 1 1
**************
0 0 0 0 1 1 0
0 1 0 0 1 1 0
1 1 1 1 0 0 0
1 1 1 1 0 0 0
0 1 0 0 0 0 0

vis배열은 정상적으로 작동되는데 bfs를 돌때

이부분에서 bfs가 끊기고

1 7 13이 되야할것이

1 2 7 11로 13의 영역이 2와 11로 나누어져서 bfs가 돌아가네요,, 코드의 어느부분이 잘못된건가요? 알려주시면 감사하겠습니다. ㅠㅠ,,

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define X first
#define Y second

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0, 1, -1, 0 };

int board[101][101];
bool vis[101][101];
vector<int> v;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int M, N, K;
	cin >> M >> N >> K;
	while (K--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int i = y1; i < y2; i++) {
			for (int j = x1; j < x2; j++) {
				board[i][j] = 1;
			}
		}
	}
	
	queue<pair<int, int>> Q;
	int count2=0;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 0 && !vis[i][j]) {
				int count1 = 0;
				Q.push({ i,j });
				vis[i][j] = 1;
				count2++;
			while (!Q.empty()) {
				pair<int, int> cur = Q.front();
				Q.pop();
				count1++;
				for (int i = 0;i < 4; i++) {
					int nx = cur.X + dx[i];
					int ny = cur.Y + dy[i];
					if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue;
					if (board[nx][ny]==1 || vis[nx][ny]==1) continue;
					Q.push({ nx,ny });
					vis[nx][ny] = 1;
				}
			}
			v.push_back(count1);
		}
		}
	}
	cout << "**************\n";
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cout << vis[i][j]<<" ";
		}
		cout << "\n";
	}
	cout << "**************\n";
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "**************\n";
	cout << count2 << "\n";
	sort(v.begin(), v.end());
	for (long unsigned int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}

	return 0;
}

wizardrabbit 2년 전 1

안녕하세요!

디버깅 결과 dx, dy 배열이 잘못되어서 탐색하는 방향이 이상하게 진행되어 결과가 다르게 출력된 것으로 보입니다.

문제의 조건에 의하면 인접한 칸으로만 탐색을 진행할 수 있으니 탐색하는 좌표는 [0, -1], [0, 1], [-1, 0], [1, 0] 이 되어야 겠지요?

그 외의 BFS 구현은 멋지게 잘 구현하셨습니다. 도움이 되었기를 바랍니다.

sss654654 2년 전 1

앗.. 너무당연하게 적어왔던 곳이라서 어디가 틀린지 감을 못잡았었네요,, 감사합니다!

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

문제

문제

출처

ICPC

bfs가 안돌아갑니다.. 도와주세용

sss654654 2년 전 0

wizardrabbit 2년 전 1

sss654654 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말