글 읽기 - c++ bfs이용해서 풀었는데 뭐가 틀렸는지 모르겠습니다.

dkxm99 1년 전 0

예제는 잘되지만 반례중 하나인

2 2 3
1 1
1 2
2 1

을 해보니 3이 아닌 2가 나옵니다. 무엇이 문제인걸까요?

위 문제는 bfs 호출이 2번 되었던걸 하나 없애고 cnt에 +1을 함으로써 해결했습니다. 그런데도 제출하면 계속 틀렸다고 나오네요... 뭐가 문제인걸까요

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#define MAX 100+1

using namespace std;

int map[MAX][MAX] = { 0, };
bool visited[MAX][MAX] = { false, };
int t, n, c;
int cnt;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

int bfs(int y, int x) {
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	visited[y][x] = true;
	while (!q.empty()) {
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= t) continue;
			if (map[ny][nx] == 1 && !visited[ny][nx]) {	
				visited[ny][nx] = true;
				cnt++;
				q.push(make_pair(ny, nx));
			}
		}
	}
	return cnt;
}

int main() {
	cin >> t >> n >> c;

	for (int i = 0; i < c; i++) {
		int mapX, mapY;
		cin >> mapY >> mapX;
		map[mapY - 1][mapX - 1] = 1;
	}
	
	for (int i = 0; i < t; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && !visited[i][j]) {
				cnt = max(cnt, bfs(i, j));
			}
		}	
	}
	cout << cnt + 1;
	return 0;
}

dkxm99 1년 전 0

cnt를 bfs 함수내에서 값을 증가시키는 용도로만 쓰고 main에서는 따로 answer라는 변수를 만들어 max값을 answer에 받으니 맞았습니다가 떳습니다.

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

문제

문제

출처

ICPC

c++ bfs이용해서 풀었는데 뭐가 틀렸는지 모르겠습니다.

dkxm99 1년 전 0

dkxm99 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말