글 읽기 - 2146 다리 만들기 반례를 못찾겠습니다

skdltm357 4년 전 0

질문게시판에 있는 반례들 다 테스트해봤는데 반례를 못찾겠어요 ..

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

int vx[4] = {1,-1,0,0};
int vy[4] = {0,0,1,-1};

int arr[101][101];
int n;
int dis=123456789;

void bfs(int y,int x,int area)
{
	queue<int> qY;
	queue<int> qX;
	qY.push(y);
	qX.push(x);
	while(!qX.empty())
	{
		int y = qY.front();
		int x = qX.front();
		qX.pop();
		qY.pop();
					
		for(int i=0;i<4;++i)
		{
			int nextY = y + vy[i];
			int nextX = x + vx[i];
			if(arr[nextY][nextX] < 0&& area != arr[nextY][nextX])
			{
					
					dis = min(dis,arr[y][x]);
			}
			else if(0<=nextY && nextY < n &&
		   	       0<=nextX && nextX < n && 
			       (arr[nextY][nextX] == 0 || arr[y][x]+1<arr[nextY][nextX]))
			{
				if(arr[y][x]<0)
				{
					arr[nextY][nextX] = 1;
				}
				else{
					arr[nextY][nextX] = arr[y][x] + 1;
				}
				
				qY.push(nextY);
				qX.push(nextX);
				
			}
		}
	}
}
void init()
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(0<arr[i][j])
			{
				arr[i][j] = 0;
			}
		}
	}
}

void solution()
{
	
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(arr[i][j]<0)
			{
				bfs(i,j,arr[i][j]);
				init();
			}
		}
	}
}

void dfs(int y,int x,int cnt)
{
	arr[y][x] = cnt;
	for(int i=0;i<4;++i)
	{
		int nextY = y+vy[i];
		int nextX = x+vx[i];
		
		if(0<=nextY && nextY < n &&
		   0<=nextX && nextX < n &&
		   arr[nextY][nextX] == 1)
		{
			dfs(nextY,nextX,cnt);
		}
	}
}

void divisionArea()
{
	int cnt = -1;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			if(arr[i][j]==1)
			{
				dfs(i,j,cnt--);
			}
		}
	}
	
}

int main()
{
	cin>>n;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			cin>>arr[i][j];
		}
	}
	divisionArea();
	solution();
	
	cout<<dis<<endl;
	
	return 0;
}

djm03178 4년 전 1

저도 반례를 못 찾겠습니다. https://www.acmicpc.net/board/... 를 한 번 읽어보고 질문을 써주신다면 찾을 수 있을지도 모르겠네요.

skdltm357 4년 전 0

앗 죄송합니다.. 코드를 제출하면 7%에서 틀렸습니다가 나옵니다.

질문게시판에 있는 반례들을 다 테스트해봐도 모두 제대로 답이 나오는데 반례가 궁금합니다.

저는 dfs를 사용하여 대륙을 각각 -1, -2, -3, ... 순서대로 값을 배열에 저장하여 구역을 나눈 후에 bfs를 사용하여 다른 대륙까지 거리를 구하는 방법으로 풀었습니다!

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

문제

문제

출처

ICPC

2146 다리 만들기 반례를 못찾겠습니다

skdltm357 4년 전 0

djm03178 4년 전 1

skdltm357 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말