글 읽기 - 반례..

gudori888 6년 전 0

문명지 각각에 번호를 붙이고,

BFS, Union-Find 사용해서 풀었는데..

2%에서 오류가 뜨는걸 봐선 기본적인 부분을 틀렸지 않나 싶어요

반례좀 들어주실 수 있나요..

#include <bits/stdc++.h>
using namespace std;

int n, k, a, b, cnt = 1, i, ans;
int mx[4] = {1, -1, 0, 0}, my[4] = {0, 0, 1, -1};
int ch[2010][2010];
int uni[100010];
int tim[2010][2010];

struct S{
	int x;
	int y;
}t;

int root(int i){
	if(uni[i] == i) return i;
	return uni[i] = root(uni[i]);
}

int merge (int u, int v){
	u = root(u);
	v = root(v);
	
	if(u==v) return 0;
	
	uni[u] = v;
	cnt++;
	
	return 1;
}

bool inrange(int x, int y){
	return x>=1 && x<=n && y>=1 && y<=n;
}

queue< S > q;

int main()
{
	scanf("%d %d", &n, &k);

	for(i=1; i<=k; i++){
		scanf("%d %d", &a, &b);
		t.x = a, t.y = b;
		ch[a][b] = uni[i] = i;
		q.push(t);
	}
	
	for(;!q.empty();){
		int x = q.front().x;
		int y = q.front().y;
		q.pop();
		
		for(i=0; i<4; i++){
			t.x = x + mx[i], t.y = y + my[i];
			if(ch[t.x][t.y]==0 && inrange(t.x, t.y)){
				q.push(t);
				ch[t.x][t.y] = ch[x][y];
				tim[t.x][t.y] = tim[x][y] + 1;
			}
			else if(ch[t.x][t.y]){
				if(merge(ch[t.x][t.y], ch[x][y]))
					ans = tim[t.x][t.y];
			}
		}
		
		if(cnt==k)
			break;
	}
	
 	printf("%d", ans);
	
	return 0;
}

cbs0615 6년 전 2

3 4

1 1
1 2
3 1
3 2

0이 뜹니당.

gudori888 6년 전 0

merge 부분에서 아래처럼 고쳐서 해결했는데 이번엔 다른 곳에서 오류가 나네요..ㅋ

ans = max(ans, tim[t.x][t.y]);

cbs0615 6년 전 1

다음 반례도 있었네요.

5 7

1 1

1 3

2 1

2 3

3 1

3 2

3 3

cbs0615 6년 전 1

저도 어제 위에 코드 수정했는데

2%에서 틀리길레 아래와 같이 수정했는데 맞네요.

#include <bits/stdc++.h>
using namespace std;

int n, k, a, b, cnt = 1, i, ans;
int mx[4] = {1, -1, 0, 0}, my[4] = {0, 0, 1, -1};
int ch[2010][2010];
int uni[100010];
int tim[2010][2010];

struct S{
	int x;
	int y;
}t;

int root(int i){
	if(uni[i] == i) return i;
	return uni[i] = root(uni[i]);
}

int merge (int u, int v){
	u = root(u);
	v = root(v);

	if(u==v) return 0;

	uni[u] = v;
	cnt++;

	return 1;
}

bool inrange(int x, int y){
	return x>=1 && x<=n && y>=1 && y<=n;
}

queue< S > q;
queue< S > tq;
int main()
{
	scanf("%d %d", &n, &k);

	for(i=1; i<=k; i++){
		scanf("%d %d", &a, &b);
		t.x = a, t.y = b;
		ch[a][b] = uni[i] = i;
		q.push(t);
	}


    while(q.size()){
        int qsize = q.size();

        for(int j = 0;j < qsize;j ++){

            int x = q.front().x, y = q.front().y;
            tq.push(q.front());
            q.pop();

            for(int jj = 0;jj < 4;jj ++){
                t.x = x + mx[jj], t.y = y + my[jj];

                if(ch[t.x][t.y]){
                    merge(ch[t.x][t.y], ch[x][y]);
                }
            }
        }

        while(tq.size()){
            int x = tq.front().x, y = tq.front().y;
            tq.pop();

            for(int jj = 0;jj < 4;jj ++){
                t.x = x + mx[jj], t.y = y + my[jj];

                if(ch[t.x][t.y] == 0 && inrange(t.x, t.y)){
                    ch[t.x][t.y] = ch[x][y];
                    q.push(t);
                }
            }
        }

        if(cnt == k) break;

        ans ++;
    }


 	printf("%d", ans);

	return 0;
}

gudori888 6년 전 0

와 진짜 감사합니다..

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

문제

문제

출처

ICPC

반례..

gudori888 6년 전 0

cbs0615 6년 전 2

gudori888 6년 전 0

cbs0615 6년 전 1

cbs0615 6년 전 1

gudori888 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말