글 읽기 - 10%에서 틀리는데 반례를 못찾겠습니다.

pwc99 5년 전 0

예제 테스트케이스 및

https://www.acmicpc.net/board/view/31422

테스트 케이스는 122451까지 맞게 나옵니다.

어떤 반례가 있을까요?

//13:15~14:20

#include <iostream>
#include <queue>

using namespace std;
//인구이동 가능한 나라들 모두 체크.
//인접한 나라 갯수 세며 인구이동 작업.

int N,L,R;
int map[55][55];
bool can_move[55][55];  //인구이동 진행할 나라 체크
bool visit[55][55]; //bfs로 인접나라 체크할 때 사용
bool moved[55][55]; //한 인구이동 과정에서 중복되지 않게 main에서 사용
int dir_r[4] = {0,0,1,-1};
int dir_c[4] = {1,-1,0,0};

void check_can_move(void) {
    int i,j,k;

    //초기화
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            can_move[i][j] = false;

    //인구이동 가능한 나라들 모두 체크.
    for(i=1;i<=N;i++) {
        for(j=1;j<=N;j++) {
            for(k=0;k<4;k++) {
                //범위 밖은 패스
                if(i+dir_r[k]<1 || i+dir_r[k]>N || j+dir_c[k]<1 || j+dir_c[k]>N)
                    continue;
                //조건 만족하면 두 나라 모두 체크
                if(abs(map[i][j] - map[i+dir_r[k]][j+dir_c[k]]) >= L &&
                    abs(map[i][j] - map[i+dir_r[k]][j+dir_c[k]]) <= R) {
                        can_move[i][j] = true;
                        can_move[i+dir_r[k]][j+dir_c[k]] = true;
                    }
            }
        }
    }
}

//인구이동하는 나라 중 한 점을 입력받아 그 나라 포함한 인구이동 진행
void move_func(int r, int c) {
    int i,j,cnt=0,sum=0;
    queue<pair<int,int>> bfs;
    queue<pair<int,int>> save_point;

    //초기화
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            visit[i][j] = false;
    
    //bfs로 인접한 나라 체크 및 갯수 세기
    bfs.push(make_pair(r,c));
    save_point.push(make_pair(r,c));
    visit[r][c] = true;
    sum += map[r][c];
    cnt++;
    while(!bfs.empty()) {
        r = bfs.front().first;
        c = bfs.front().second;
        bfs.pop();
        for(i=0;i<4;i++) {
            //범위 이탈 or 이미 방문 or can_move가 아닌 경우
            if(r+dir_r[i]<1 || r+dir_r[i]>N || c+dir_c[i]<1 || c+dir_c[i]>N ||
                visit[r+dir_r[i]][c+dir_c[i]] || !can_move[r+dir_r[i]][c+dir_c[i]])
                continue;
            bfs.push(make_pair(r+dir_r[i],c+dir_c[i]));
            save_point.push(make_pair(r+dir_r[i],c+dir_c[i]));
            visit[r+dir_r[i]][c+dir_c[i]] = true;
            sum += map[r+dir_r[i]][c+dir_c[i]];
            cnt++;
        }
    }
    //인구이동 작업. sum/cnt로 모두 셋팅
    while(!save_point.empty()) {
        r = save_point.front().first;
        c = save_point.front().second;
        save_point.pop();
        map[r][c] = sum/cnt;
        moved[r][c] = true;
    }
}

int main(void) {
    int i,j,result_cnt=0;
    bool flag;
    //입력
    cin>>N>>L>>R;
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
            cin>>map[i][j];
    
    while(1) {
        //초기화
        flag = false;
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                moved[i][j] = false;
        
        //인구이동 가능한 나라들 모두 체크.
        check_can_move();

        //인구이동 더이상 없으면 탈출
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                if(can_move[i][j])
                    flag = true;
        
        if(!flag) {
            cout<<result_cnt;
            break;
        }
        
        //인접한 나라 갯수 세며 인구이동 작업. 인구이동 안한 나라 하나씩 move_func()
        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                if(!moved[i][j] && can_move[i][j])
                    move_func(i,j);
        
        result_cnt++;
    }

    return 0;
}

soph456 5년 전 15

이 반례는 어떠세요

4 1 9
96 93 74 30
60 90 65 96
5 27 17 98
10 41 46 20
correct: 1

(96,93,90)->93
(74,65)->69
(96,98)->97
(5,10)->7
(41,46)->43

/************/
5 1 5
88 27 34 84 9
40 91 11 30 81
2 88 65 26 75
75 66 16 14 28
89 10 5 30 75
correct: 1

(91,88)->89
(30,26)->28
(16,14)->15
(10,5)->7

pwc99 5년 전 2

아아 감사합니다.

덕분에 어느 부분이 잘못된지 알았습니다!

인구이동을 따로 해줘야하는데 인접한지만 확인하고 바로 다 합쳐버렸네요ㅠㅠ

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

문제

문제

출처

ICPC

10%에서 틀리는데 반례를 못찾겠습니다.

pwc99 5년 전 0

soph456 5년 전 15

pwc99 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말