글 읽기 - 어디가 틀렸을까요?? 반례있으신분 부탁드려요ㅜㅜ

greeneye 6년 전 0

설계가 잘 못된 것이가요?
예제는 맞는데, 어떤 반례에서 틀리는지 알기가 어렵네요 ㅜㅜ

/*
1113 수영장 만들기
수영장 만들 곳 크기 엔엠

1. 한칸씩 들어온 맵에서 부터 시작해서,
2. 1을 찾습니다. 1 뭉치를 찾습니다.
3. 뭉치를 둘러싼 벽중에 가장 낮은 점을 찾습니다.
4. 그 뭉치들을 가장 낮은 점수까지 채워주고, 이것을 ans 의 값에 더해줍니다.

이것을 1에서 8까지 반복하면 되겠습니다.

*/

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define SIZE 55 // 55
int map[SIZE][SIZE];
int visit[SIZE][SIZE];
struct point {
	int x, y;
};
int front, rear;
int N, M;
point que[SIZE * SIZE];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int ans;
string str;
int x, y, nx, ny;
int minVal = 2123456789;

void problemIn() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int j = 0; j < M; j++) {
			map[i][j] = str[j] - '0';
		}
	}
}

void visit_init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			visit[i][j] = 0;
		}
	}
}


void bfs(int k) {

	// 같은 숫자들 뭉치를 찾고,
	while (front != rear) {
		front++;
		x = que[front].x;
		y = que[front].y;
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= 1 && ny >= 1 && nx < (N - 1) && ny < (M - 1)) {
				if (visit[nx][ny] == 0 && map[nx][ny] == k) {
					visit[nx][ny] = 1;
					rear++;
					que[rear].x = nx;
					que[rear].y = ny;
				}
			}
		}
	}

	// 그 주변의 가장 작은 숫자를 다시 탐색합니다.
	front = -1;
	minVal = 2123456789;
	while (front != rear) {
		front++;
		x = que[front].x;
		y = que[front].y;
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < (N - 1) && ny < (M - 1)) {
				if (visit[nx][ny] == 0) {
					minVal = min(minVal, map[nx][ny]);
				}
			}
		}
	}

	if (minVal > k) {
		// 그럼 다시 그 뭉치를 가장 작은 수까지 올립니다.
		for (int i = 0; i <= rear; i++) {
			ans += minVal - map[que[i].x][que[i].y];
			map[que[i].x][que[i].y] = minVal;
		}
	}



}


void solve() {

	front = rear = -1;
	for (int k = 1; k < 9; k++) {
		visit_init();
		for (int i = 1; i < (N - 1); i++) {
			for (int j = 1; j < (M - 1); j++) {
				front = rear = -1;

				if (map[i][j] == k && visit[i][j] == 0) {
					rear++;
					visit[i][j] = 1;
					que[rear].x = i;
					que[rear].y = j;
					bfs(k);
				}
			}
		}
	}

}

int main() {
	problemIn();
	solve();
	cout << ans << endl;
	return 0;
}

junho0406 6년 전 0

잘 하세요

juhongkim2 6년 전 10

5 5
59995
95549
94449
95449
88888

답 : 33

질문자님 코드는 42나옵니다.

그리고

@junho0406님 답변 겁나 싸가지 없으시네요

greeneye 6년 전 0

감사합니다. 다시 한번 수정해볼게요!!

greeneye 6년 전 0

와우 둘러쌓인 벽중에 최소값을 찾는 부분에서 인덱스를 잘 못 넣었던 것을 찾앗습니다!!
감사합니다 ^^!!!

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

문제

문제

출처

ICPC

어디가 틀렸을까요?? 반례있으신분 부탁드려요ㅜㅜ

greeneye 6년 전 0

junho0406 6년 전 0

juhongkim2 6년 전 10

greeneye 6년 전 0

greeneye 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말