글 읽기 - 런타임 에러(Out of Bounds)

wony6731 3년 전 0

BFS를 이용하여 edge들을 구한 다음 MST 를 이용하여 풀었습니다.

개인적으로 Out of Bounds가 의심되는 부분은

'S'를 '2', 'K'를 '3...'으로 표현하여 ------ (line 88)

'S'를 index 0, 'K'를 Index 1부터 매칭되도록 --------- (line 59)

하였습니다.

어떠한 부분에서 Out of Bounds가 발생하는지 알 수 있을까요

/*
* @Desc
*	복제 가능 구역 : 출발지, 열쇠
*/
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;
string board[50];
vector<pair<int, pair<int, int>>> edge;
int p[251];	// idx 0 is 'S' and 1...250 is 'K'

int FindParent(int x) {
	if (p[x] == x) return x;
	return p[x] = FindParent(p[x]);
}

void Union(int x, int y) {
	x = FindParent(x);
	y = FindParent(y);

	if (x < y) p[y] = x;
	else p[x] = y;
}

bool IsSameParent(int x, int y) {
	x = FindParent(x);
	y = FindParent(y);
	if (x == y) return true;
	else return false;
}

void GetEdge() {
	bool visited[50][50];
	queue<pair<int, pair<int, int>>> Q;
	int dx[4] = { 0,0,1,-1 };
	int dy[4] = { 1,-1,0,0 };
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == '0' || board[i][j] == '1') continue;

			while (!Q.empty()) Q.pop();
			memset(visited, false, sizeof(visited));
			visited[i][j] = true;
			Q.push({ 0,{i,j} });
			while (!Q.empty()) {
				int x = Q.front().second.second;
				int y = Q.front().second.first;
				int dist = Q.front().first;
				Q.pop();
				
				if (!(i == y && j == x) && board[y][x] >= '2') {
					edge.push_back({ dist, {(int)board[i][j] - 50, (int)board[y][x] - 50} });
				}

				for (int dr = 0; dr < 4; dr++) {
					int nx = x + dx[dr];
					int ny = y + dy[dr];

					if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
					if (visited[ny][nx]) continue;
					if (board[ny][nx] == '1') continue;

					visited[ny][nx] = true;
					Q.push({ dist + 1,{ny,nx} });
				}
			}
		}
	}
}

void Init() {
	char val = '3';
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> board[i];
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 'S') {
				board[i][j] = '2';
			}
			else if (board[i][j] == 'K') {
				board[i][j] = val++;
			}
		}
	}
	GetEdge();
}

bool cmp(const pair<int, pair<int, int>>& a, const pair<int, pair<int, int>>& b) {
	return a.first < b.first;
}

void MST() {
	for (int i = 0; i <= M; i++)
		p[i] = i;
	
	sort(edge.begin(), edge.end(), cmp);

	int cnt = 0;
	int sum = 0;
	for (int i = 0; i < edge.size(); i++) {
		int v1 = edge[i].second.first;
		int v2 = edge[i].second.second;
		int dist = edge[i].first;

		if (IsSameParent(v1, v2)) continue;
		Union(v1, v2);
		cnt++;
		sum += dist;
	}
	if(cnt == M)
		cout << sum;
	else cout << "-1";
}

int main() {
	Init();
	MST();
}

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

문제

문제

출처

ICPC

런타임 에러(Out of Bounds)

wony6731 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말