글 읽기 - 1926번 BFS문제 어디서 틀렸는지 모르겠습니다!

wpwns0805 1년 전 0

예제 출력결과가 자꾸 4, 1이 나오는데 뭐가 잘못된걸까요 ㅠㅠ

항상 답해주시는분들 감사드립니다.

#include <iostream>
#include <queue>

int n, m;
int arr[500][500] = { 0, };
bool visited[500][500] = { false, };
int count = 0;
int maxv = 0;

int BFS(int i, int j) {
	int dy[] = { 0,1,0,-1 };
	int dx[] = { 1,0,-1,0 };
	int result = 1;
	std::queue<std::pair<int, int> > q;
	q.push({ i,j });
	while (!(q.empty())) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (arr[nx][ny] == 1 && visited[nx][ny] == false) {
					visited[nx][ny] = true;
					result++;
					q.push({ nx,ny });
				}
			}
		}
	}

	return result;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	std::cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> arr[i][j];
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 1 && visited[i][j] == false) {
				visited[i][j] = true;
				count++;
				if (BFS(i, j) > maxv) {
					maxv = BFS(i, j);
				}

			}
		}
	}

	std::cout << count << '\n';
	std::cout << maxv;
}

wpwns0805 1년 전 0

아 코드 다시 한번 읽어보니 해결되었습니다!

51번째줄에 BFS를 if문에 바로 넣지않고,

BFS(i,j)를 value에 저장한다음, if(value > maxv) maxv = value 하니까 바로 값이 나왔습니다

adung7 1년 전 1

51,52번째줄에서 if조건이 만족할때 BFS함수가 한번 더 실행되게 됩니다.

이때 if조건때 이미 BFS가 실행된 상태이므로 visited배열이 이미 true로 바뀐 상태여서 작성자님이 원하는 결과가 대입되지 않습니다.

이를 따로 변수를 두어 2번실행되지 않게 해주시면 해결됩니다.

wpwns0805 1년 전 0

adung7님 감사합니다! 항상 답변주시는분들 감사드립니다.

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

문제

문제

출처

ICPC

1926번 BFS문제 어디서 틀렸는지 모르겠습니다!

wpwns0805 1년 전 0

wpwns0805 1년 전 0

adung7 1년 전 1

wpwns0805 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말