글 읽기 - 12%에서 틀리는데 반례가 궁금합니다.

kth990303 2년 전 1

유니온 파인드를 이용해 상하좌우 결합할 때,

merge 함수에서 최소값을 가진 좌표로 갱신할 수 있도록, 값이 같다면 visit이 더 작은(더 오래된) 좌표로 갱신할 수 있도록 코드를 짰습니다.

반례나 틀린 점을 찾습니다. 아예 알고리즘이 틀렸을 가능성도 있을 것 같긴 합니다만... ㅠㅠ

감사합니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAX = 1001;
int N, M, Q, p[MAX * MAX], d[MAX * MAX];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int visit[MAX * MAX];
int find(int a) {
	if (a == p[a])
		return a;
	return p[a] = find(p[a]);
}
bool merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return false;
	if (d[a] > d[b])
		swap(a, b);
	else if (visit[a] > visit[b])
		swap(a, b);
	p[b] = a;
	return true;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M >> Q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
            // 0,0부터 N-1, M-1까지로 바꿔 진행하였습니다.
            // 일차원 배열로 바꿔 진행하였습니다.
            // (2, 3)일 경우 (1, 2)->p[6]=6;
			cin >> d[i * M + j + 1];
			p[i * M + j + 1] = i * M + j + 1;
		}
	}
	for (int q = 1; q <= Q; q++) {
		int i, j, c;
		cin >> i >> j >> c;
		i--; j--;
		int num = i * M + j + 1;
		d[num] -= c;
        // visit배열이 작을수록 더 오래 전
		visit[num] = q;
        // 상하좌우 탐색
		for (int k = 0; k < 4; k++) {
			int nx = j + dx[k];
			int ny = i + dy[k];
			int nnum = ny * M + nx + 1;
			if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                // 인접한 칸도 비가 내린 곳인경우
				if (visit[nnum]) {
                    // 이미 같은 컴포넌트에 속한 경우이나 부모를 바꿔줘야 하는 경우는
                    // 부모를 바꿔주기 위해 또 진행합니다.
					if (!merge(nnum, num) && d[num]<d[nnum]) {
						p[num] = num;
						merge(nnum, num);
					}
                    // 좌표값도 같으나 더 예전꺼가 있어 부모값을 바꿔줘야하는 경우
					else if (!merge(nnum, num) && d[num] == d[nnum]) {
						if (visit[num] < visit[nnum]) {
							p[num] = num;
							merge(nnum, num);
						}
					}
				}
			}
		}
		int ans = find(num);
        // 현재 소나기가 내린 좌표의 부모값의 좌표를 출력합니다.
		cout << (ans - 1) / M + 1 << " " << (ans - 1) % M + 1 << "\n";
	}
}

littlesam95 2년 전 1

혹시 푸셨으면 죄송합니다.

num과 nnum이 이미 묶여 있는 상황에서 높이의 최솟값을 비교할 때

d[num] < d[nnum]이 아니라 d[num] < d[find(nnum)]으로 해야 할 것 같습니다.

그룹에서 가장 높이가 낮고 비가 내린 지 오래 된 칸을 parent로 기록하고 num을 parent의 높이와 비가 내린 시간과 비교해야 하는데

형님이 작성하신 코드는 num을 parent의 높이와 비가 내린 시간과 비교하지 않는 것 같아서 말씀드립니다..

2차원 배열로 해결하려 했다가 덕분에 1차원 배열로 변경해서 해결했습니다 감사합니다!

kth990303 2년 전 1

답변 감사합니다.
다만 nnum 부분을 수정해도 잘 안되네요 ㅜㅜ 바꾼 제 코드를 올려드릴테니, 혹시나 틀린 점이 보인다면 한번 체크해주시면 감사하겠습니다 (다만, 이 작업이 여간 귀찮은 게 아닐테니 패스하셔도 괜찮습니다 :)

나중에 각잡고 다시 한 번 풀어봐야겠어요.

제 질문글 관심있게 봐주셔서 다시 한 번 감사드립니다!

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 1007;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int N, M, Q, p[MAX*MAX], d[MAX*MAX];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int vis[MAX*MAX];
int find(int a) {
    if (a == p[a])
        return a;
    return p[a] = find(p[a]);
}
bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return false;
    if (d[a] > d[b])
        swap(a, b);
    else if (vis[a] > vis[b])
        swap(a, b);
    p[b] = a;
    return true;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>N>>M>>Q;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> d[i * M + j + 1];
            p[i * M + j + 1] = i * M + j + 1;
        }
    }
    for(int q=1;q<=Q;q++){
        int i,j,c;
        cin>>i>>j>>c;
        i--;j--;
        int num=i*M+j+1;
        d[num]-=c;
        vis[num]=q;
        for(int k=0;k<4;k++){
            int nx = j + dx[k];
            int ny = i + dy[k];
            int nnum = ny * M + nx + 1;
            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (vis[nnum]) {
                    if (!merge(nnum, num) && d[num]<d[find(nnum)]) {
                        p[num]=num;
                        p[find(num)]=find(num);
                        merge(find(nnum), num);
                    }
                    else if (!merge(nnum, num) && d[num]==d[find(nnum)]) {
                        if (vis[num] < vis[find(nnum)]) {
                            p[num]=num;
                            p[find(num)]=find(num);
                            merge(find(nnum), num);
                        }
                    }
                }
            }
        }
        int ans = find(num);
        cout << (ans - 1) / M + 1 << " " << (ans - 1) % M + 1 << "\n";
    }
}

littlesam95 2년 전 1

음 제 얕은 지식으로는 잘 모르겠지만

merge하는 부분에서 조건문이 약간 이상한 것 같기도 한데...

if (d[a] > d[b])
swap(a, b);
else if (vis[a] > vis[b]) <- 여기서 d[a]가 d[b]와 같은 경우만 비가 내린 시간을 따지는 건데, 조건문이 이렇게 된다면 d[a] < d[b]인 경우에도 비가 내린 시간을 따지게 되지 않나요?
swap(a, b);

제가 맞게 생각한 건지 모르겠습니다ㅠ

kth990303 2년 전 1

오잉 그러네요.

그 부분만 추가하니까 AC를 받네요

덕분에 맞았어요ㅋㅋㅋ
코드 신경써서 봐주셔서 감사드립니다!

kth990303 2년 전 1

원래 코드에서도 merge 하는 부분을 조금 수정하니까 제대로 ac를 받는 걸 확인했습니다!

맨처음 코드에서 merge하는 과정에서 nnum 자체가 find함수를 돌기 때문에 parent를 찾아간 상태에서 비교를 하는 거여서 d[find(nnum)]으로 안해도 돌아가는 것 같아요.

merge 함수에서 알고리즘 실수가 있었네요 다시 한 번 관심있게 코드 봐주셔서 감사드립니다 :)

littlesam95 2년 전 1

아하 그렇군요 감사합니다! 저도 덕분에 많이 배웠습니다

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

문제

문제

출처

ICPC

12%에서 틀리는데 반례가 궁금합니다.

kth990303 2년 전 1

littlesam95 2년 전 1

kth990303 2년 전 1

littlesam95 2년 전 1

kth990303 2년 전 1

kth990303 2년 전 1

littlesam95 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말