글 읽기 - 2667 반례부탁드립니다 ㅠㅠㅠ

greeneye 6년 전 0

주어진 입력은 정답을 도출하는데, 제출하면 틀립니다. 라고 나옵니다.

어디가 잘 못 되었을까요?ㅜㅜㅜㅜ

/*
오께이 재귀로 큐를 사용하지 않고 풀어보도록 하겠습니다. 이때가 지금 01 입니다 처음 만나는
01 입니다 이것에 대해서 하나의 dfs 로 들어가도록 하겠습니다.
1이면 arr[1]++
2이면 arr[2]++
3이면 arr[3]++
*/

#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int map[30][30];
int check[30][30];
int n, x, y, nx, ny;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int cnt;
int arr[20];

struct points {
	int x, y;
};
queue<points> que;

void problemIn() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
}

void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && check[i][j]==0) {
				cnt++;
				que.push({ i,j });
				while (!que.empty()) {
					x = que.front().x;
					y = que.front().y;
					que.pop();
					for (int i = 0; i < 4; i++) {
						nx = x + dx[i];
						ny = y + dy[i];
						if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
							if (map[nx][ny] == 1 && check[nx][ny] == 0) {
								check[nx][ny] = cnt;
								que.push({ nx,ny });
							}
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (check[i][j] == 1)
				arr[0]++;
			else if (check[i][j] == 2) {
				arr[1]++;
			}
			else if (check[i][j] == 3) {
				arr[2]++;
			}
		}
	}
	sort(arr, arr + cnt);
	cout << cnt << endl;
	for (int i = 0; i < cnt; i++) {
		cout << arr[i] << endl;
	}
}

int main() {
	problemIn();
	solve();
	return 0;
}

chogahui05 6년 전 1

어떠한 알고리즘을 어떻게 쓰셨는지..

주석에 설명이라도 달아놓으시지.. 어짜피 바로 보였으니까 상관은 없는데..

(1) 일단 이어져 있는 연결 요소(?) 같은 게 딱 3개라는 보장두 없고요.

(2) 코드가 유지보수 하기 어렵게 짜여져 있네요.

이게 겁나 쉬운 문제에서는 저렇게 짜도 되는데.. 어려운 문제는 답도 없어요.

아예 기능을 나누세요.

어디서부터 BFS나 DFS를 수행할 건지. 그리고 만약에 BFS를 수행했다면

탐색 크기를 리턴하는 함수 등을 만들면 좋겠죠?

greeneye 6년 전 0

와우 감사합니다. 조언 귀 담아 듣고 수정해보도록 하겠습니다!!!

djm03178 6년 전 1

그리고 질문을 올릴 때 문제 번호를 적는 칸이 따로 있는데, 여기에 써주시면 링크가 바로 걸려 답변자들에게 편해집니다.

greeneye 6년 전 0

아 옙 수정했습니다. 감사합니다!

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

문제

문제

출처

ICPC

2667 반례부탁드립니다 ㅠㅠㅠ

greeneye 6년 전 0

chogahui05 6년 전 1

greeneye 6년 전 0

djm03178 6년 전 1

greeneye 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말