글 읽기 - 반례를 구합니다!

swrho 2년 전 0

제 나름대로 괜찮은 반례를 다 넣어보았지만 문제 없이 잘 돌아갔습니다. 저의 알고리즘에 문제가 있는 듯 합니다만 잘 찾을수 없어서 글 올립니다.

저는 유니온 파인드와 bfs 를 썼는데요,

1 - '.' 부분을 집합별로 숫자로 나타낸다 (makeNum 함수 구현)

2 - 주변에 X 인것을 골라 큐에 넣어준다 (putQueue 함수 구현)

3 - BFS 구현

3 - 1 - 얼음을 녹이는 과정에서 근처에 다른 집합 (num[][]) 의 얼음이 있으면 merge 를 해준다

3 - 2 - 같은 집합이 되면 함수를 종료하고 답을 도출한다

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <memory.h>

using namespace std;

struct swan {
	int x, y, n, d;
};
queue<swan> Q;
int P[1200000];
int R, C, dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
char sea[1505][1505];
int num[1505][1505], L1_num, L2_num;
int visit[1505][1505];
void DFS(int x, int y, int n) {
	if (num[x][y] != 0)
		return;
	if (x < 0 || y < 0 || x >= R || y >= C)
		return;
	if (sea[x][y] == 'X')
		return;
	if (sea[x][y] == 'L') {
		if (L1_num == 0)
			L1_num = n;
		else
			L2_num = n;
	}
	num[x][y] = n;
	DFS(x + 1, y, n);
	DFS(x - 1, y, n);
	DFS(x, y + 1, n);
	DFS(x, y - 1, n);
}
void makeNum(void) {
	int n = 1;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if ((sea[i][j] == '.' || sea[i][j] == 'L') && num[i][j] == 0) {
			
				DFS(i, j, n++);
			}
		}
	}
}
int nearX(int x, int y) {
	for (int d = 0; d < 4; d++) {
		if (sea[x + dx[d]][y + dy[d]] == 'X') {
			return 1;
		}
	}
	return 0;
}
void putQueue(void) {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (num[i][j] != 0) {
				if (nearX(i, j)) {
					visit[i][j] = 1;
					Q.push({ i,j,num[i][j],0 });
				}
			}
		}
	}
}
int find(int x) {
	if (P[x] == -1) return x;
	P[x] = find(P[x]);
	return P[x];
}
void merge(int x, int y) {
	int a = find(x);
	int b = find(y);
	if (a == b)
		return;
	P[a] = b;
}
int nearNum(int x, int y, int dir, int n) {
	for (int d = 0; d < 4; d++) {
		if (num[x + dx[d]][y + dy[d]] != 0) {
			if (num[x + dx[d]][y + dy[d]] != n) {
				return num[x + dx[d]][y + dy[d]];
			}
		}
	}
	return 0;
}
int BFS(void) {

	while (!Q.empty()) {
		swan cur;
		cur = Q.front();
		Q.pop();
		for (int d = 0; d < 4; d++) {
			swan next = cur;
			next.x += dx[d], next.y += dy[d];
			next.d++;
			if (next.x < 0 || next.y < 0 || next.x >= R || next.y >= C)
				continue;
			if (visit[next.x][next.y] == 1)
				continue;
			if (sea[next.x][next.y] == 'X') {
				visit[next.x][next.y] = 1;
				num[next.x][next.y] = next.n;
				//merge or not
				sea[next.x][next.y] = '.';
				int near = nearNum(next.x, next.y, d, num[next.x][next.y]);
				if (near != 0) {
					merge(next.n, near);
					// 여기서 함수를 종료할지 말지 쓰자
					if (find(L1_num) == find(L2_num))
						return next.d;
				}
				Q.push(next);
			}
		}
	}

}
int main() {
	memset(P, -1, sizeof(P));
	cin >> R >> C;
	for (int i = 0; i < R; i++)
		scanf("%s", &sea[i]);
	makeNum();
	int a = 0;
	putQueue();
	cout << BFS();

}

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

문제

문제

출처

ICPC

반례를 구합니다!

swrho 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말