글 읽기 - 어느 로직이 틀렸을까요....

culture1123 4년 전 0

첫번째 bfs를 이용하여 초기에 인접해 잇는지 검사

두번째로 bfs로 인접해 있는지 검사하는 식으로 풀었습니다.

어디가 틀렸는지 모르겠습니다 도와주세요....

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
struct go {
	int x;
	int y;
	int cnt;
};
int map[2001][2001];
int parent[100001];
int n, m;
queue<go> st;
queue<go> q;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int Find(int x)
{
	if (parent[x] == x) return x;
	return parent[x] = Find(parent[x]);
}

void Union(int x, int y)
{
	x = Find(x);
	y = Find(y);
	if (x == y)
		return;
	if (x != y)
	{
		if (x < y)
		{
			parent[y] = x;
		}
		else
		{
			parent[x] = y;
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}
	int cnt = 0;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		map[y][x] = ++cnt;
		st.push({ y,x,0 });
		q.push({ y,x,0 });
	}
	//초기에 합쳐져 있나 검사
	while (!st.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().cnt;
		st.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dr[i];
			int ny = y + dc[i];
			if (nx< 1 || ny<1 || nx>n || ny>n)
				continue;
			if (map[nx][ny] != 0 && map[nx][ny] != map[x][y]) {
				if (Find(map[nx][ny]) != Find(map[x][y])) {
					Union(map[nx][ny], map[x][y]);
					cnt--;
				}

			}
		}
	}
	//초기에 바로 정답이라면 정답출력
	if (cnt == 1)
	{
		cout << "0" << endl;
		return 0;
	}
	//초기에 정답이 아니라면 다 합쳐질때까지 동작
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int z = q.front().cnt;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dr[i];
			int ny = y + dc[i];
			int ncnt = z + 1;
			if (nx< 1 || ny<1 || nx>n || ny>n)
				continue;
			if (map[nx][ny] != 0)
				continue;
			if (map[nx][ny] == 0)
			{
				map[nx][ny] = map[x][y];
				q.push({ nx,ny,ncnt });
				for (int j = 0; j < 4; j++)
				{
					int nnr = nx + dr[j];
					int nnc = ny + dc[j];
					if (nnr< 1 || nnc<1 || nnr>n || nnc>n)
						continue;
					if (map[nnr][nnc] == 0)
						continue;
					if (map[nnr][nnc] != map[nx][ny])
					{
						if (Find(map[nnr][nnc]) != Find(map[nx][ny]))
						{
							Union(map[nnr][nnc], map[nx][ny]);
							cnt--;
							if (cnt == 1)
							{
								cout << ncnt << endl;
								return 0;
							}
						}
					}
				}
			}


		}

	}
}

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

문제

문제

출처

ICPC

어느 로직이 틀렸을까요....

culture1123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말