글 읽기 - 1743 음식물 피하기(dfs) 어디가 틀렸는지 모르겠습니다

bok03220 5년 전 1

주어진 데이터 넣어보고, 제가 임의로 데이터 넣어보고 그래도 틀렸다고 나올 때가 참 난처하네요.

주변에 물어볼 사람도 없고 ㅠㅠ

값은 제대로 나오는 것 같은데, 사소한 부분에서 오류가 나나봅니다.

힌트라도 주시면 감사하겠습니다!!!

// 181005, KKambi, 1743, 음식물 피하기
#include <iostream>
#include <string.h>
using namespace std;

int n, m, k, big, ans=0;	// 세로 길이와 가로 길이 (<=100), 음식물 쓰레기 개수(<=10,000)
int garbage[101][101];

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

void dfs(int row, int col);
int max(int a, int b);

int main() {
	// 세로 길이 =  행의 개수, 가로 길이 = 열의 개수
	cin >> n >> m >> k;

	// 음식물 쓰레기 위치 입력받기
	memset(garbage, 0, sizeof(garbage));
	for (int i = 1; i <= k; i++) {
		int x, y;
		cin >> x >> y;
		garbage[y][x] = 1;
	}

	// componet 돌면서 dfs 돌때마다 음식물 크기 올리기
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			big = 0;
			if (garbage[i][j] == 1) {
				dfs(i, j);
			}
			ans = max(ans, big);
		}
	}
	cout << ans << endl;
	return 0;
}

void dfs(int row, int col) {
	garbage[row][col] = 0;
	big++;
	for (int i = 0; i < 4; i++) {
		int newRow, newCol;
		newRow = row + dx[i]; newCol = col + dy[i];
		if (newRow >= 1 && newCol >= 1 && newRow <= n && newCol <= m
			&& garbage[newRow][newCol])
			dfs(newRow, newCol);
	}
}

int max(int a, int b) {
	return a > b ? a : b;
}

/*
	1. 음식물은 근처에 있는 것끼리 뭉쳐, 하나의 큰 음식물 쓰레기가 된다.
	2. 떨어진 음식물 중에 제일 큰 음식물을 피해 가려고 한다.
	3. 인접 = 상하좌우 인접

	Q. 음식물 중 가장 큰 음식물의 크기는?

	4. 각 연결 요소에 대해 dfs를 돌리면서, 크기를 저장하면 된다.
*/

djm03178 5년 전 2

우선 27~32, 39번째 줄 때문에 무조건 틀립니다. 제출하실 때 지우신 거라면, 질문글을 쓸 때도 반드시 제출한 버전으로 올려주세요.

그 외에는 24번째 줄만 [y][x] -> [x][y]로 바꾸면 맞습니다.

bok03220 5년 전 0

djm03178님 감사합니다!

제출할 때의 버전으로 수정하였습니다.

한국어로 번역된 문제에는 '음식물이 떨어진 좌표'가 주어진다고 하길래

저는 당연히 (x,y) 좌표가 주어지는 줄 알고, [y][x]로 입력받았습니다.

그런데 답변을 보고 나서 이상하다 싶어 원문을 봤더니

좌표가 아닌 row, column이 주어지는 것이더라구요.

사실 아래의 힌트를 보고 알아챌 수는 있었는데, 테스트 케이스와 별개로 주어지는 것이라 생각해서

그냥 넘겨버렸었네요.

앞으로는 좀 더 꼼꼼하게 조건을 살펴보도록 하겠습니다. 감사합니다!

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

문제

문제

출처

ICPC

1743 음식물 피하기(dfs) 어디가 틀렸는지 모르겠습니다

bok03220 5년 전 1

djm03178 5년 전 2

bok03220 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말