글 읽기 - 형님들 제 머리로는 도저히 반례를 못찾겠어요..

dlwkdgjs 6년 전 0

일단 dps 로 각 섬 묶음 단위로 인데스 번호를 부여 했어요

2 2 2 0 0 0 0 0 3 3 33

0000 00 0 0 00 0 0 00

0 0 0 00 04 444 0000

대충이런식으로 0은 바다 2~4는 각 섬묶음의 인덱스 번호요

그로 bps 로 len_map배열로 1칸으로 갈수있는곳 마크하는 식으로 계산했는데

반례좀 찾아주세요 사랑합니다 ㅜㅜ 모지란 저를 용서해주세요 하루를 투자해도 안됩띠다..

#include <iostream>
#include <deque>
#pragma warning(disable:4996);
using namespace std;
int num;
int map[101][101];
int visit[101][101];
int len_map[101][101];
deque<int*>que;
int k;
int len = 0;

void bps(int a, int b) {

	visit[a][b] = k;
	
	if (!visit[a + 1][b] && map[a + 1][b] && (a+1<num)) {
		bps(a+1,b);
	}
	if (!visit[a - 1][b] && map[a - 1][b] && (a-1>=0)) {
		bps(a - 1, b);
	}
	if (!visit[a][b+1] && map[a][b+1] && (b+1<num)) {
		bps(a, b+1);
	}
	if (!visit[a][b-1] && map[a][b-1] && (b-1>=0)) {
		bps(a, b-1);
	}
}


int min_bridge() {
	k = 2;
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			if (map[i][j] && !visit[i][j]) {
				bps(i, j);
				k++;
			}
		}
	}
	//섬을 파싱했어
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			if (!map[i][j]) {//대륙겉면의 0
				if (map[i - 1][j] && ( (i-1)>=0 )) {//아래에 1이있으면 push
					int* p = new int[4];
					p[0] = i-1; p[1] = j; p[2] = visit[i-1][j];	p[3] = len;
					que.push_back(p);
					continue;
				}
				if (map[i +1][j]  && ((i+1)< num)) {//위
					int* p = new int[4];
					p[0] = i+1; p[1] = j; p[2] = visit[i+1][j];	p[3] = len;
					que.push_back(p);
					continue;
				}
				if (map[i][j+1] && ( (j+1)<num ) ) {//오른쪽
					int* p = new int[4];
					p[0] = i; p[1] = j+1; p[2] = visit[i][j+1];	p[3] = len;
					que.push_back(p);
					continue;
				}
				if (map[i][j-1] && ((j-1)>=0)) {//왼쪽
					int* p = new int[4];
					p[0] = i; p[1] = j-1; p[2] = visit[i][j-1];	p[3] = len;
					que.push_back(p);
					continue;
				}
			}
		}
	}

	while (!que.empty()) {
		int sz = que.size();
		len++;

		for (int i = 0; i < sz; i++) {
			int* p = que.front();
			int a = p[0]; int b = p[1]; int c = p[2]; int d= p[3];
			que.pop_front();

			if (visit[a + 1][b] && ((a+1) <num)) {
				if (visit[a][b] != visit[a + 1][b]) {
					return len_map[a][b] + len_map[a + 1][b];
				}
			}
			if (visit[a - 1][b]  && ((a-1)>=0)) {
				if (visit[a][b] != visit[a - 1][b]) {
					return len_map[a][b] + len_map[a - 1][b];
				}
			}
			if (visit[a][b + 1] && ((b+1)<num)) {
				if (visit[a][b] != visit[a][b + 1]) {
					return len_map[a][b] + len_map[a][b+1];
				}
			}
			if (visit[a][b - 1] && ((b-1)>=0)) {
				if (visit[a][b] != visit[a][b - 1]) {
					return len_map[a][b] + len_map[a][b-1];
				}
			}

			if (!visit[a + 1][b] && ( (a+1)<num)) {
				int* p = new int[4];
				p[0] = a + 1; p[1] = b; p[2] = visit[a][b];//a,b로(o)
				p[3] = len;
				len_map[a+1][b]=len;
				que.push_back(p);
				visit[a + 1][b] = p[2];
			}
			if (!visit[a - 1][b] && ( (a-1)>=0)) {
				int* p = new int[4];
				p[0] = a - 1; p[1] = b; p[2] = visit[a][b];//a,b로(o)
				p[3] = len;
				len_map[a - 1][b] = len;
				que.push_back(p);
				visit[a - 1][b] = p[2];
			}
			if (!visit[a][b + 1] && ((b+1)<num)) {
				int* p = new int[4];
				p[0] = a; p[1] = b + 1; p[2] = visit[a][b];//a,b로(o)
				p[3] = len;
				len_map[a][b+1] = len;
				que.push_back(p);
				visit[a][b + 1] = p[2];
			}
			if (!visit[a][b - 1] && (b-1)>=0) {
				int* p = new int[4];
				p[0] = a; p[1] = b - 1; p[2] = visit[a][b];//a,b로(o)
				p[3] = len;
				len_map[a][b-1] = len;
				que.push_back(p);
				visit[a][b - 1] = p[2];
			}
		}

	}
	return 0;
}


int main() {
	
	scanf("%d", &num);

	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			scanf("%d",&map[i][j]);
		}
	}

	printf("%d",min_bridge());
	return 0;
}

hjhlevelup 6년 전 0

문제를 잘못이해하셨네요.

처음부터 꼼꼼하게 다시 읽어보시고 푸시길 바랍니다.

dlwkdgjs 6년 전 0

형님 여러 섬들이있으면 그중 2개의 섬을 연결하는 1개의 다리의 길이가 최소가 되게하는 그 다리의 길이를 출력하는거 아닌가요..?

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

문제

문제

출처

ICPC

형님들 제 머리로는 도저히 반례를 못찾겠어요..

dlwkdgjs 6년 전 0

hjhlevelup 6년 전 0

dlwkdgjs 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말