글 읽기 - 채점하자 마자 '틀렸습니다.'가 뜹니다.

kgy94k 3년 전 0

테스트 케이스, 게시판 반례 모두 확인했는데 답은 잘 나옵니다.

하지만, 채점시 바로 틀려버리네요ㅜㅜ

제 코드나 논리에 문제가 어떤 문제가 있는지 알려주시면 정말 감사하겠습니다!!

주석으로 코드의 의도를 작성해뒀지만 혹시 이해가 안되거나 이상한 부분이 있다면 지적해주세요!!

이전 문제는 해결) 섬 모두 연결되었는지 확인을 제대로 안해줬네요.. 연결 확인하니 22% 까지는 맞습니다.

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int MAT[11][11], dist[7][7], visit[2][11][11];
//MAT: 섬 번호 붙여서 저장하는 지도, dist: 각 두 개 섬의 거리를 저장, visit: 두 섬의 거리를 측정하는 과정중 중복을 피하기 위해 사용
int dr[] = { 0, 1 ,0 ,-1 }, dc[] = { 1, 0, -1, 0 };
int connect_island[7];
int mark, sum, ans;

vector <pair<int, int>> vec[7]; //각 섬을 구성한 위치(R, C)를 저장하는 벡터

void dist_cnt(int island) { //island: 거리를 세기 위해 시작하는 섬
	int num = vec[island].size(); //섬을 구성하는 위치들을 벡터로 저장한 것
	for (int i = 0; i < num; i++) { //섬을 구성하는 각 위치에서 인근 섬과의 거리 측정
		for (int n = 0; n < 4; n++) { //동, 서, 남, 북 네 방향 탐색
			int R = vec[island][i].first; int C = vec[island][i].second;
			int cnt = 0;
			while (true) { //인근에 있는 섬이 있는지, 있다면 거리를 계산
				R = R + dr[n]; C = C + dc[n];
				if (R < 1 || R > N || C < 1 || C > M ||
					visit[n % 2][R][C] == 1 || MAT[R][C] == island) {
					break;
				}
				visit[n % 2][R][C] = 1; 
				// ex) 1번 섬에서 3번 섬, 3번 섬에서 1번 섬의 거리 측정시 반복 과정을 피하기 위해 사용
				if (MAT[R][C] >= 1 && MAT[R][C] != island) { // 만약 다른 번호의 섬을 만난 경우
					int next = MAT[R][C];
					if (cnt >= 2) { // 거리가 2 이상이 경우만 저장
						if (dist[island][next] == 10 || cnt < dist[island][next]) { // 두 섬 사이의 최소 거리 저장
							dist[island][next] = cnt;
							dist[next][island] = cnt;
						}
					}
					break;
				}
				cnt++;
			}
		}
	}
}

void connect(int island, int num) {
	if (num == mark) {
		if (ans == -1 || ans > sum) {
			ans = sum;
		}
	}
	else {
		for (int i = 1; i <= mark; i++) {
			if (connect_island[i] == 1 || dist[island][i] == 10) { //섬의 방문 여부와 다리 건설 가능성 확인
				continue;
			}
			connect_island[i] = 1;
			sum = sum + dist[island][i];
			connect(i, num + 1); // 다음으로 연결된 다리에서 그 다음 다리로 연결하기 위함
			connect(island, num + 1); // 현재 다리에서 또 다른 다리를 연결하기 위함
			sum = sum - dist[island][i];
			connect_island[i] = 0;
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &MAT[i][j]);
			if (MAT[i][j] == 1) { //섬 번호 marking을 위해 1을 -1로 저장
				MAT[i][j] = -1;
			}
			visit[0][i][j] = 0; visit[1][i][j] = 0; //초기화
		}
	}
	/*섬에 번호 붙이기*/
	queue <pair<int, int>> que; 
	mark = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (MAT[i][j] != -1) { 
				continue;
			}
			while (!que.empty()) { //초기화
				que.pop();
			}
			mark++;
			vec[mark].clear(); //초기화
			que.push(make_pair(i, j));
			MAT[i][j] = mark;
			vec[mark].push_back(make_pair(i, j));
			while (!que.empty()) {
				int R = que.front().first; int C = que.front().second;
				que.pop();
				for (int n = 0; n < 4; n++) {
					int nR = R + dr[n]; int nC = C + dc[n];
					if (nR <1 || nR > N || nC < 1 || nC > M || MAT[nR][nC] != -1) {
						continue;
					}
					MAT[nR][nC] = mark;
					que.push(make_pair(nR, nC));
					vec[mark].push_back(make_pair(nR, nC));
				}
			}
		}
	}
	/*초기화*/
	for (int i = 1; i <= mark; i++) { 
		connect_island[i] = 0;
		for (int j = 1; j <= mark; j++) {
			dist[i][j] = 10;
		}
	}

	ans = -1; sum = 0;

	/*각 섬 사이의 최소 거리 찾기*/
	for (int i = 1; i <= mark; i++) {
		dist_cnt(i);
	}
	/*섬 사이를 연결하기*/
	for (int i = 1; i <= mark; i++) {
		connect_island[i] = 1;
		connect(i, 1);
		connect_island[i] = 0;
	}
	
	printf("%d", ans);
}

tjsgh1512 1년 전 0

저도 제출하자마자 바로 틀렸습니다가 나오는데 혹시 어떤 게 문제였나요???

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

문제

문제

출처

ICPC

채점하자 마자 '틀렸습니다.'가 뜹니다.

kgy94k 3년 전 0

tjsgh1512 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말