글 읽기 - 유기농 배추 C++ BFS로 구현했는데 실패로 뜹니다..ㅠㅠ 반례가 있을까요?

kjhh03 4년 전 0

어디서 문제가 일어나는지를 모르겠습니다.. ㅠㅠ

넣어본 테스트 케이스 : 3 1 1 1 0 0 2 2 2 0 0 1 1 5 5 6 0 0 0 1 0 2 2 0 5 5 1 3 >> 밑과 동일

1 1 1

0 0

2 2 2

0 0

1 1

5 5 6

0 0

0 1

0 2

2 0

5 5

1 3

#include <iostream>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

int dxy[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int arr[51][51];
int M, N, K, answer;

void bfs(int x, int y) {
	queue<pair <int, int>> que;
	que.push(make_pair(x, y));
	int dx, dy;
	while (!que.empty()) {
		for (int i = 0; i < 4; i++) {
			dx = que.front().second + dxy[i][0];
			dy = que.front().first + dxy[i][1];
			if (dx >= 0 && dx < 51 && dy >= 0 && dy < 51 && arr[dy][dx] == 1) {
				que.push(make_pair(dy, dx));
				arr[dy][dx] = arr[que.front().first][que.front().second] + 1;
			}
		}
		que.pop();
	}
}

void solution() {
	answer = 0;
	memset(arr, 0, sizeof(arr));
	cin >> M >> N >> K;
	for (int i = 0; i < K; i++) {
		int x, y;
		cin >> x >> y;
		arr[x][y] = 1;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 1) {
				answer++;
				bfs(i, j);
			}
		}
	}
	
	cout << answer << "\n";
//	for (int i = 0; i < M; i++) {
//		for (int j = 0; j < N; j++) {
//			cout << arr[i][j] <<" ";
//		}
//		cout << "\n";
//	}

}

int main(int argc, char* argv[]) {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		solution();
	}
}

djm03178 4년 전 1

36번째 줄만 x y의 위치를 바꾸면 맞습니다.

kjhh03 4년 전 0

감사합니다.. ㅠㅠ 배열에서 행열과 x축 y축 생각하는게 자꾸 헷깔리네요.. 실수하지 않도록 주의해야겠습니다.

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

문제

문제

출처

ICPC

유기농 배추 C++ BFS로 구현했는데 실패로 뜹니다..ㅠㅠ 반례가 있을까요?

kjhh03 4년 전 0

djm03178 4년 전 1

kjhh03 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말