글 읽기 - 1012 배추밭 어디가 틀린지 모르겠습니다 제발 도와주세요

yd9506 3년 전 0

문제에 나와있는 예시는 전부 맞았다고 나오고, 질문 검색에서 나오는 반례들도 최대한 시도해본 결과 맞았다고 나옵니다

가장 경계선에서 에러가 많이 발생하기 때문에 (0,0), (0,49), (49,0), (49,49)에 대한 값들도 정확하게 처리하는 것으로 보이고, 0인 경우도 정확히 출력했는데 어디서 틀린건지 감이 안잡힙니다.

반례를 찾아 주시면 정말 감사하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 50

using namespace std;

int T, M, N, K;		// 테스트케이스 T, 
int map[MAX][MAX];
int visited[MAX][MAX];

void dfs(int n, int m) {
	visited[n][m] = true;
	//cout << "(" << n << ", " << m << ") 방문" << endl;
	//동쪽
	if (m + 1 < M && !visited[n][m + 1] && map[n][m + 1] == 1) {
		dfs(n, m + 1);
	}
	//서쪽
	if (m - 1 >= 0 && !visited[n][m - 1] && map[n][m - 1] == 1) {
		dfs(n, m - 1);
	}
	//남쪽
	if (n + 1 < N && !visited[n + 1][m] && map[n + 1][m] == 1) {
		dfs(n + 1, m);
	}
	//북쪽
	if (n - 1 >= 0 && !visited[n - 1][m] && map[n - 1][m] == 1) {
		dfs(n - 1, m);
	}
}

int dfs() {
	fill(&visited[0][0], &visited[N][M], false);
	int components = 0;
	for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
			if (!visited[n][m] && map[n][m] == 1) {
				components++;
				dfs(n, m);
			}
		}
	}
	return components;
}

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> M >> N >> K;
		fill(&map[0][0], &map[N-1][M], 0);

		for (int k = 0; k < K; k++) {
			int m, n;
			cin >> m >> n;
			map[n][m] = 1;
		}
		/*
		cout << "배추밭" << endl;
		for (int n = 0; n < N; n++) {
		for (int m = 0; m < M; m++) {
		cout << map[n][m] << " ";
		}
		cout << endl;
		}
		*/

		cout << dfs() << endl;
	}
}

yd9506 3년 전 0

상세하게 리뷰해주셔서 너무 감사드립니다!! BFS로도 한번 풀어보도록 하겠습니다.

제가 이전에 DFS로 풀어 성공한 경험이 있었는데 이번엔 실패라고 나오길래 혹시 제가 모르는 원인이 있나, 코드를 구현할 때 빠트린 부분이 있나 궁금해서 질문했었습니다.

BFS로 풀면서 DFS, BFS 실력을 더 향상시켜 보겠습니다.

정성스럽게 답변해주셔서 정말 너무 감사드립니다. ㅠㅠ 몇번 해보다 안되니까 질문하는 제 자신에 대해 반성하는 계기가 되었습니다. 한번 더 찾아보고 저도 원인 찾으면 말씀드리겠습니다!!

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

문제

문제

출처

ICPC

1012 배추밭 어디가 틀린지 모르겠습니다 제발 도와주세요

yd9506 3년 전 0

yd9506 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말