글 읽기 - C++ 런타임 원인을 모르겠습니다 ㅠ

kim031504 3년 전 0

아무리 찾아봐도 배열의 인덱스 범위를 넘어갈 만한 부분이 보이지 않습니다 ㅠ

한 번 더 검토해봐도 행 N 과 열 M을 헷갈린 부분도 없구요 ㅠㅠ

배열 인덱스로 인한 런타임 에러 외의 부분이 있을까요...?

아무리 찾아도 제 역량으로 보이지 않습니다 ㅠ

도와주시면 감사하겠습니다! ㅠ

p.s

유니온 파인드, BFS, 최소 신장 트리 알고리즘으로 접근하였습니다.

테스트 케이스는 잘 나옵니다.

자세한 코드의 설명은 주석으로 달아놨습니다!

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

using namespace std;

struct Position {
	int r;
	int c;
};

struct Edge {
	int u;
	int v;
	int w;
};

const int dr[] = { 1, -1, 0, 0 };
const int dc[] = { 0, 0, 1, -1 };

int map[10][10];
int labeled_map[10][10];

// 유니온 파인드를 위한 변수
vector<Edge> e;
int parent[7];

int N, M;

// 간선을 가중치 기준으로 오름차순 정렬
bool comp(const Edge &edge1, const Edge &edge2) {
	if (edge1.w < edge2.w)
		return true;
	else
		return false;
}

// Find(x) : x로 들어온 원소의 root 노드를 반환
int Find(int x) {
	// root인 경우 x를 반환
	if (x == parent[x])
		return x;

	// 아니면 root를 찾아감
	int p = Find(parent[x]);
	parent[x] = p;

	return p;
}

// Union(x, y) : x원소와 y원소를 합치는 함수로 y의 root 노드를 x로 한다
bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x != y) {
		parent[y] = x;
		return true;
	}

	return false;
}

bool isInside(int r, int c) {
	if (0 <= r && r < N && 0 <= c && c < M)
		return true;

	return false;
}

void labeling(int r, int c, int cnt) {
	queue<Position> q;
	q.push({ r, c });
	labeled_map[r][c] = cnt;

	while (!q.empty()) {
		r = q.front().r;
		c = q.front().c;

		q.pop();

		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];

			if (!isInside(nr, nc))
				continue;

			// 이미 라벨링 되어있는 경우
			if (labeled_map[nr][nc])
				continue;

			// 땅이 아닌 경우
			if (!map[nr][nc])
				continue;

			q.push({ nr, nc });
			labeled_map[nr][nc] = cnt;
		}
	}
}

// 기준 숫자가 들어왔을 때, 
// 기준 숫자에서 상하좌우로 갔을 때 닿는 애들이 있는지 확인하고
// 있으면 벡터 e에 넣어준다!
void findEdge(int num) {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < M; c++) {
			if (labeled_map[r][c] == num) {
				for (int k = 0; k < 4; k++) {
					int tmp_r = r;
					int tmp_c = c;
					int cnt = 0;	// 다리 길이를 위함

					while (true) {
						int nr = tmp_r + dr[k];
						int nc = tmp_c + dc[k];

						// 범위를 벗어나면 탐색 종료!
						if (!isInside(nr, nc)) 
							break;

						// 바로 옆에 나랑 같은 숫자면 나가고
						if (labeled_map[nr][nc] == num)
							break;

						// 현재 나가고자 하는 방향이 바다면 다리 놓고 이동
						if (map[nr][nc] == 0) {
							cnt++;
							tmp_r = nr;
							tmp_c = nc;

							continue;
						}

						// 바다도 아니고 나 자신 육지도 아니고 새로운 육지가 나오면
						// 그리고 놓은 다리 길이가 2 이상이면
						if (cnt > 1)
							e.push_back({ num, labeled_map[nr][nc], cnt });

						break;
					}
				}
			}
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			cin >> map[i][j];

	/* 라벨링 작업! */
	int cnt = 0;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (map[i][j] == 1 && labeled_map[i][j] == 0)
				labeling(i, j, ++cnt);

	/* 유니온 파인드 배열 parent 자기 자신을 root로 초기화 */
	for (int i = 1; i <= cnt; i++)
		parent[i] = i;

	/* 간선 정보 입력 */
	for (int i = 1; i <= cnt; i++)
		findEdge(i);

	// 만일 간선 정보가 담기지 않았다면 연결이 불가능한 것이다
	if (e.size() == 0) {
		cout << -1 << '\n';
		return 0;
	}

	// 간선을 가중치 기준으로 오름차순 정렬
	sort(e.begin(), e.end(), comp);

	int ans = 0;	// 가중치 합
	int edge_cnt = 0;	// 뽑은 간선 수
	int idx = 0;	// 간선 인덱스

	while (true) {
		if (Union(e[idx].u, e[idx].v)) {
			ans += e[idx].w;
			edge_cnt++;

			// 총 노드(cnt) 개수 - 1개의 간선을 뽑으면 작업 끝!
			if (edge_cnt == cnt - 1)
				break;
		}

		idx++;
	}

	cout << ans << '\n';

	return 0;
}

3587jjh 3년 전 1

문제 번호가 안나와있습니다

kim031504 3년 전 0

아! 수정했습니다!

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

문제

문제

출처

ICPC

C++ 런타임 원인을 모르겠습니다 ㅠ

kim031504 3년 전 0

3587jjh 3년 전 1

kim031504 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말