글 읽기 - [런타임에러] 고수님들 도와주세요 2

hanil0623 4년 전 0

어디서 런타임 에러가 나는지 모르겠습니다.. 도와주세요!

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n, m, cnt = 1, sum = 0, temper = 0, node = 0;
int map[11][11] = { 0, };
int check[11][11] = { 0, };
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int p[7];
struct info {
	int x, y;
};

// v는 섬의 개수, v[i]엔 i번째 섬에 해당하는 땅의 좌표가 기록되어 있다.
vector<info> v[7];

// 크루스칼 알고리즘을 쓰기 위해 만든 벡터, 거리<노드, 노드> 기록
vector<pair<int, pair<int, int> > > vt;

void bfs(info t, int cnt);
int searching_island(int srt, int goal);
void Kruskal(int num);
int getParent(int a);
void unionSet(int a, int b);

int main() {
	info t;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] && !check[i][j]) {
				t.x = i; t.y = j;
				bfs(t, cnt++);
			}
		}
	}
	
	for (int i = 1; i < cnt; i++) {
		for (int j = i+1; j < cnt; j++) {
			// 섬끼리 이어진 다리가 있는지 조사하는 함수
			temper = searching_island(i, j);
			if (temper >= 2 && temper != 1e9) {
				
				vt.push_back(make_pair(temper, make_pair(i, j)));
			}
		}
	}
	// 크루스칼을 쓰기 위한 소팅과정
	for (int i = 1; i <= cnt - 1; i++) { p[i] = i; }
	sort(vt.begin(), vt.end());

	Kruskal(cnt-1);
	if (sum == 1e9) {
		cout << -1 << endl;
		return 0;
	}
	
	cout << sum << endl;

	return 0;
}

void Kruskal(int num) {
	int counter = 0;
	int index = 0;
	int size = vt.size();
	int distance = 0;
	int u, v;

	while (counter < num - 1) {
		if (index == size) {
			sum = 1e9;
			break;
		}

		distance = vt[index].first;
		u = vt[index].second.first;
		v = vt[index].second.second;

		index++;
		if (getParent(u) == getParent(v)) {
			continue;
		}
		else {
			unionSet(u, v);
			
			counter++;
			sum += distance;

		}
	}
}

int getParent(int a) {
	if (p[a] == a) return a;
	return p[a] = getParent(p[a]);
}

void unionSet(int a, int b) {
	int rootA = getParent(a);
	int rootB = getParent(b);
	p[rootA] = rootB;
}

// 섬들의 번호를 check에 매기기 위한 함수
void bfs(info t, int cnt) {
	queue<info> q;
	info a;

	check[t.x][t.y] = cnt;
	q.push(t);
	v[cnt].push_back(t);

	while (!q.empty()) {
		a = q.front(); q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nx = a.x + dx[i];
			int ny = a.y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (check[nx][ny] || !map[nx][ny]) continue;
			
			a.x = nx; a.y = ny;
			q.push(a);
			v[cnt].push_back(a);
			check[nx][ny] = cnt;
		}
	}

}

// srt 넘버의 섬과 goal 넘버의 섬 사이의 거리의 최솟값을 찾아 반환하는 함수
int searching_island(int srt, int goal) {
	int min_dist = 1e9;

	for (int i = 0; i < v[srt].size(); i++) {
		for (int j = 0; j < 4; j++) {
			int dist = 0;
			int x = v[srt][i].x; int y = v[srt][i].y;
			int nx = x + dx[j]; int ny = y + dy[j];

			while (1) {
				if (nx < 0 || nx >= n || ny < 0 || ny >= m) { break; }
				
				if (check[nx][ny] == srt || check[nx][ny] == 0 || check[nx][ny] == goal) {
					if (check[nx][ny] == goal) {
						if (dist >= 2) {
							min_dist = min(min_dist, dist);
						}
						break;
					}

					if (!map[nx][ny]) {
						dist++;
					}
				}
				else {
					break;
				}
				x = nx; y = ny;
				nx = x + dx[j]; ny = y + dy[j];
			}
		}
	}
	return min_dist;
}

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

문제

문제

출처

ICPC

[런타임에러] 고수님들 도와주세요 2

hanil0623 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말