글 읽기 - 문명문제의 두 코드 비교

hansx2079 5년 전 0

주석으로 나눈 두 소스중 위에것은 제가짠 코드 아래것은 어떤분이 짠코드입니다.

그런데 두코드 구조가 거의 대부분 똑같다고 생각되는데

그 위에 코드는 틀렸다고 나오고 아래 코드는 맞았다고 나오네요

두 코드에서 구조적? 그 흐름의 차이가 뭐가있을까요 ?

#include<iostream>
#include<queue>
using namespace std;

int N, K, M;
int Par[100005], Rank[100005];
int World[2005][2005];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
bool Range(int x, int y)
{
	if (x < 1 || x > N || y < 1 || y > N) return false;
	return true;
}
struct Vec
{
	int x, y;
};
queue<Vec> q;
int find(int x)
{
	if (x == Par[x])
	{
		return x;
	}
	return Par[x] = find(Par[x]);
}

bool unions(int x, int y)
{
	x = find(x), y = find(y);
	if (x == y)return false;
	if (Rank[y] > Rank[x])
		Par[x] = y;
	else
	{
		Par[y] = x;
	}
	if (Rank[x] == Rank[y])Rank[x]++;

	return true;

}
int main()
{
	for (int i = 0; i < 100001; i++)Par[i] = i;
	cin >> N >> K;
	for (int i = 1; i <= K; i++)
	{//초기화
		int x, y;
		cin >> x >> y;
		World[x][y] = i;
		q.push({ x,y });
		for (int o = 0; o < 4; o++)
		{//처음 문명 합병
			int tx = x + dx[o], ty = y + dy[o];
			if (Range(tx, ty) && World[tx][ty] != 0)
			{
				if (unions(World[tx][ty], World[x][y]))
					M++;
			}
		}
	}
	int c = 0;
	while (true) {
		if (M == K - 1)break; // 문명이 하나일때 탈출 
		c++;
		int qs = q.size();
		for (int i = 0; i < qs; i++) {
			int qx = q.front().x, qy = q.front().y; q.pop();

			for (int o = 0; o < 4; o++) {
				int tx = qx + dx[o], ty = qy + dy[o];
				if (Range(tx, tx)) {
					if (World[tx][ty] == 0) {
						World[tx][ty] = World[qx][qy];


						for (int j = 0; j < 4; j++) {
							int ttx = tx + dx[j], tty = ty + dy[j];
							if (Range(ttx, tty) && World[ttx][tty] != 0 && World[tx][ty] != World[ttx][tty]) {
								if (unions(World[ttx][tty], World[tx][ty])) {
									M++;
								}
							}
						}
						q.push({ tx,ty });
					}
				}
			}
		}
	}
	cout << c << endl;
}
//위코드
/////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
//아래코드
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct Data {
	int y, x;
};


int n, k,m;
int _map[2005][2005];
int chk[2005][2005];
int p[100005];
int dy[4] = { 1,0,-1,0 };
int dx[4] = { 0,1,0,-1 };

int _find(int x) {
	if (p[x] == x)return x;
	return p[x] = _find(p[x]);
}
bool _union(int x, int y) {
	x = _find(x);
	y = _find(y);
	if (x == y)return false;
	p[x] = y;
	return true;
}
bool Range(int y, int x) {
	if (y<1 || x<1 || y>n || x>n)return false;
	return true;
}
queue<Data>q;
int main() {
	for (int i = 0; i < 100001; i++)p[i] = i;

	scanf("%d %d", &n, &k);
	for (int i = 0; i < k; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		_map[a][b] = i+1;
		q.push({ a,b });

		for (int j = 0; j < 4; j++) {
			int ny = a + dy[j];
			int nx = b + dx[j];
			if (Range(ny, nx) && _map[ny][nx]!=0){
				if (_union(_map[ny][nx], _map[a][b])) {
					m++;
				}
			}
		}
	}
	int t = 0;
	
	while (1) {
		if (m == k - 1)break;
		t++;
		int _size = q.size();
		for (int s = 0; s < _size; s++) {
			Data now = q.front();	q.pop();


			for (int i = 0; i < 4; i++) {
				int ny = now.y + dy[i];
				int nx = now.x + dx[i];

				if (Range(ny, nx)) {
					if (_map[ny][nx] == 0) {
						_map[ny][nx] = _map[now.y][now.x];

						for (int j = 0; j < 4; j++) {
							int nny = ny + dy[j];
							int nnx = nx + dx[j];
							if (Range(nny, nnx) && _map[ny][nx] != _map[nny][nnx] && _map[nny][nnx] != 0) {
								if (_union(_map[ny][nx], _map[nny][nnx])) {
									m++;
								}
							}
						}
						q.push({ ny,nx });
					}
				}
			}
		}
	}
	cout << t << endl;
	return 0;
}

nonamed 5년 전 0

73번째 줄에

if (Range(tx, tx)) {

이 부분을

if (Range(tx, ty)) {

로 고치시면 될 듯 합니다...

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

문제

문제

출처

ICPC

문명문제의 두 코드 비교

hansx2079 5년 전 0

nonamed 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말