글 읽기 - c++) 삼성 기출문제 반례 부탁드립니다. (10%)

enoch9 3년 전 1

찾아본 테스트케이스 다 통과하는데 10퍼센트 뜨네요.

1. 지역을 구분하여 번호를 매긴다.

2. 지역끼리 연결이 되는 지, 연결이 된다면 최소 길이가 몇인지 따진 후 c[지역1][지역2] = 길이 로 저장한다.

3. c[][]로 연결된 것들 중 DFS로 몇 개의 쌍들을 빼가며 최소 연결 거리를 찾는다.

이 로직으로 했는데 어디가 잘못되었을까요..!!!

#if 1
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
int n, m, a[100][100], c[100][100], landcnt, minn = 987654321, sum;
//c[1][2] = 3 : 1,2의 거리는 3
vector <pair <int, int> > land[100]; //land[0][0] = 1,3: 0번째 섬의 0번째 구성요소는 1,3이다. 
vector <pair <int, int>> cland; // cland[0] = 1,2 : 1,2가 연결됨.
bool visited[100][100], tmpv[100];
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
queue <pair <int, int>> q;

void BFS(int x_, int y_) {
	q.push(make_pair(x_, y_));
	visited[x_][y_] = true;
	land[landcnt].push_back(make_pair(x_, y_));
	a[x_][y_] = landcnt + 1;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
			if (visited[xx][yy]) continue;
			if (a[xx][yy] == 1) {
				q.push(make_pair(xx, yy));
				visited[xx][yy] = true;
				a[xx][yy] = landcnt + 1;
				land[landcnt].push_back(make_pair(xx, yy));
			}
			
		}
	}

	if (!q.empty())while (!q.empty()) q.pop();
}

void makemindist() {
	for (int i = 0; i < landcnt; i++) {
		for (int j = 0; j < land[i].size(); j++) {
			int x = land[i][j].first;
			int y = land[i][j].second;
			int xx = x;
			int yy = y;
			int cnt = 0;
			while (xx - 1 >= 0) { //왼쪽으로 가기
				xx -= 1;
				cnt++;
				if (a[xx][y] == a[x][y]) break;
				if (cnt - 1 >= c[a[xx][y]][a[x][y]]) break; //이미 구해놓은 길이보다 길면.
				if (a[xx][y] != 0) {
					if (cnt <= 2) break;
					else {
						if (c[a[xx][y]][a[x][y]] == 987654321) {
							cland.push_back(make_pair(a[x][y], a[xx][y]));
						}
						c[a[xx][y]][a[x][y]] = cnt - 1;
						c[a[x][y]][a[xx][y]] = cnt - 1;
					}
				}
			}
			xx = x;
			cnt = 0;
			while (xx + 1 < n) { //오른쪽으로 가기
				xx += 1;
				cnt++;
				if (a[xx][y] == a[x][y]) break;
				if (cnt - 1 >= c[a[xx][y]][a[x][y]]) break; //이미 구해놓은 길이보다 길면.
				if (a[xx][y] != 0) {
					if (cnt <= 2) break;
					else {
						if (c[a[xx][y]][a[x][y]] == 987654321) {
							cland.push_back(make_pair(a[x][y], a[xx][y]));
						}
						c[a[xx][y]][a[x][y]] = cnt - 1;
						c[a[x][y]][a[xx][y]] = cnt - 1;
					}
				}
			}
			xx = x;
			cnt = 0;
			while (yy - 1 >= 0) { //위로 가기
				yy -= 1;
				cnt++;
				if (a[x][yy] == a[x][y]) break;
				if (cnt - 1 >= c[a[x][yy]][a[x][y]]) break; //이미 구해놓은 길이보다 길면.
				if (a[x][yy] != 0) {
					if (cnt <= 2) break;
					else {
						if (c[a[x][yy]][a[x][y]] == 987654321) {
							cland.push_back(make_pair(a[x][y], a[x][yy]));
						}
						c[a[x][y]][a[x][yy]] = cnt - 1;
						c[a[x][yy]][a[x][y]] = cnt - 1;
					}
				}
			}
			yy = y;
			cnt = 0;
			while (yy + 1 < m) { //아래로 가기
				yy += 1;
				cnt++;
				if (a[x][yy] == a[x][y]) break;
				if (cnt - 1>= c[a[x][yy]][a[x][y]]) break; //이미 구해놓은 길이보다 길면.
				if (a[x][yy] != 0) {
					if (cnt <= 2) break;
					else {
						if (c[a[x][yy]][a[x][y]] == 987654321) {
							cland.push_back(make_pair(a[x][y], a[x][yy]));
						}
						c[a[x][y]][a[x][yy]] = cnt - 1;
						c[a[x][yy]][a[x][y]] = cnt - 1;
					}
				}
			}
			yy = y;
		}

	}
}

bool isconnected() {
	queue <int> qq;
    for (int i = 0; i<100; i++) tmpv[i] = false;
	tmpv[1] = true;
	for (int i = 2; i <= landcnt; i++) {
		if (c[1][i] != 987654321) {
			qq.push(i);
			tmpv[i] = true;
		}
	}
	while (!qq.empty()) {
		int x = qq.front();
		qq.pop();
		for (int i = 1; i <= landcnt; i++) {
			if (tmpv[i]) continue;
			if (x == i) continue;
			if (c[x][i] != 987654321) {
				qq.push(i);
				tmpv[i] = true;
			}
		}
	}

	if (!qq.empty()) while (!qq.empty()) qq.pop();

	for (int i = 1; i <= landcnt; i++) {
		if (!tmpv[i]) return false;
	}
	return true;
}

int DFS(int idx, int tsum) {
	if (isconnected() == false) return -1;

	minn = min(tsum, minn);

	if (idx + 1 >= cland.size()) return 1;

	for (int i = idx + 1; i < cland.size(); i++) {
		int xx = cland[i].first;
		int yy = cland[i].second;
		int his = c[xx][yy];
		c[xx][yy] = 987654321;
		c[yy][xx] = 987654321;
		DFS(i, tsum - his);
		c[xx][yy] = his;
		c[yy][xx] = his;
	}
	return 1;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	//섬만들기
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j] && a[i][j] == 1) {
				BFS(i, j);
				landcnt++;
			}
		}
	}

	for (int i = 0; i <= landcnt; i++) {
		for (int j = 0; j <= landcnt; j++) {
			c[i][j] = 987654321;
			c[j][i] = 987654321;
		}
	}

	//printf("\n");
	//for (int i = 0; i < n; i++) {
	//	for (int j = 0; j < m; j++) {
	//		printf("%d ", a[i][j]);
	//	}
	//	printf("\n");
	//}

	//섬 간 최소거리 저장
	makemindist();
    
	if (isconnected() == false) {
		printf("-1\n");
		return 0;
	}
    
	for (int i = 0; i < cland.size(); i++) {
		//printf("c[%d][%d] = %d \n", cland[i].first, cland[i].second, c[cland[i].first][cland[i].second]);
		sum += c[cland[i].first][cland[i].second];
	}


	//DFS로 빼본다.
	DFS(-1, sum);

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

#endif

enoch9 3년 전 0

해결했습니다.

상, 하, 좌, 우로 가보면서 0이 아닌 것을 찾았을 때 c[출발한 섬][도달한섬] = 거리라고 처리했었는데, 여기에서 break;를 걸어주지 않았더니 1 0 0 2 0 0 3 과 같은 경우 1이 3과 연결되었었네요. ^^

MST 공부하고, 반례 만드는 것을 훈련해야겠습니다.

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

문제

문제

출처

ICPC

c++) 삼성 기출문제 반례 부탁드립니다. (10%)

enoch9 3년 전 1

enoch9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말