글 읽기 - 틀립답 어디서 문제일까요 ? ㅠㅠ

eodlsgh123 3년 전 0

주어진 TC하고 질문 게시판 반례는 맞는거 같은데 어느 부분에서 문제가 생기는 걸까요 ? 도와주세요 ㅠㅠ

1. whil 을 통해 더이상 합칠 영역이 없을 때 가지 인구이동

2. 인구이동시에는 BFS를 통하여 최대 어느 영역까지 합칠 수 있는지 탐색

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

using namespace std;
struct Node{ int y, x; };
int n, l, r;
int map[50][50];
int visit[50][50] = { 0 };
int check[4][2] = {
	1, 0,
	-1, 0,
	0, 1,
	0, -1
};

void bfs(int y, int x, int c){
	int flag = 0;
	int sum = 0;
	int userCnt = 0;
	visit[y][x] = c;
	queue<Node> qu;
	qu.push({ y, x });

	while (1){
		if (qu.empty() == true) break;
		Node now = qu.front();
		sum += map[now.y][now.x];
		++userCnt;
		for (int i = 0; i < 4; ++i){
			int dy = now.y + check[i][0];
			int dx = now.x + check[i][1];
			if (dy >= 0 && dx >= 0 && dy < n && dx < n && visit[dy][dx] == 0){
				int res = abs(map[now.y][now.x] - map[dy][dx]);
				if (res >= l && res <= r){
					visit[dy][dx] = c;
					qu.push({ dy, dx });
				}
			}
		}
		qu.pop();
	}

    // 합칠 영역의 인구수 map에 갱신
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (visit[i][j] == c){
				map[i][j] = sum / userCnt;
			}
		}
	}
}

bool checkList(){
	int pr = 0;

	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			if (visit[i][j] == pr) return false;
			else pr = visit[i][j];
		}
	}
	return true;
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	int cpMap[50][50] = { 0 };
	cin >> n >> l >> r;
	int cnt = 0;
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < n; ++j){
			cin >> map[i][j];
		}
	}
	int rCnt = 0;
    
	while (1){
		int c = 0;
		memcpy(visit, cpMap, 4 * 50 * 50);
        // 합쳐진 영역은 visit에 check 
		for (int i = 0; i < n; ++i){
			for (int j = 0; j < n; ++j){
				if (visit[i][j] == 0) {
					bfs(i, j, ++c);
				}
			}
		}
        // 만약 더이상 합칠 곳이 없다면 종료
		if (checkList() == true){
			printf("%d", rCnt);
			return 0;
		}
        // 합칠 곳이 있다면 인구이동 횟수 1 증가
		else{
			++rCnt;
		}
	}
}

boboya98 3년 전 0

stdafx.h ...

eodlsgh123 3년 전 0

에디터에서 복붙한거라 죄송해요 수정했어요

hooya 3년 전 3

반례

2 10 20

0 30

50 10

0 20

50 20

10 10

50 20

10 15

50 15

answer : 3

~~(그와중 저도 아직 못맞았습니다)~~

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

문제

문제

출처

ICPC

틀립답 어디서 문제일까요 ? ㅠㅠ

eodlsgh123 3년 전 0

boboya98 3년 전 0

eodlsgh123 3년 전 0

hooya 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말