글 읽기 - 1261 알고스팟 런타임에러 원인을 정말 모르겠습니다 도와주세요

hek0628 4년 전 0

방 하나를 하나의 정점이라고 생각하고 (0, 0)을 정점 0, (n, m)을 정점 (n * m - 1)로 해서 n * m개의 정점을 가진 그래프로 만들어줬습니다.

간선의 가중치는 벽을 부수는 것은 1, 벽을 부수지 않는 것은 0, 인접하지 않은 방은 무한대(INF)로 주고 인접리스트 adj에 저장했습니다.

가중치가 가장 적은 것부터 선택할 수 있도록 우선순위 큐를 사용했습니다.

우선 순위 큐에서 정렬을 할 때 가중치가 적은 것부터 오름차순 정렬될 수 있도록 pair의 first는 가중치, second는 향하는 정점 이렇게 했습니다.

그러고 나서 다익스트라 알고리즘을 돌렸습니다.

로직은 문제가 없는 것 같은데 런타임 에러가 어디에서 나는지 도무지 모르겠습니다.

뭐가 문제일까요? 도와주시면 정말 감사하겠습니다.

#include <iostream>
#include <string>
#include <map>
#include <tuple>
#include <vector>
#include <queue>
using namespace std;


int main() {
	int m, n;
	cin >> m >> n;
	vector<string> input(n);
	for (int i = 0; i < n; i++) {
		cin >> input[i];
	}
	const int INF = 200;
	vector<int> length(n * m, INF);
	vector<bool> visited(n * m, false); 
	vector<pair<int, int>> adj[100]; //인접리스트. adj[from]에는 가중치와 to정점을 pair로 묶어서 저장

	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (input[i][j] == '1') adj[i * m + j - 1].push_back(make_pair(1, i * m + j));
			else adj[i * m + j - 1].push_back(make_pair(0, i * m + j));
			if (input[i][j - 1] == '1') adj[i * m + j].push_back(make_pair(1, i * m + j - 1));
			else adj[i * m + j].push_back(make_pair(0, i * m + j - 1)); 
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (input[j][i] == '1') adj[j * m + i - m].push_back(make_pair(1, j * m + i)); 
			else adj[j * m + i - m].push_back(make_pair(0, j * m + i));
			if (input[j - 1][i] == '1') adj[j * m + i].push_back(make_pair(1, j * m + i - m));
			else adj[j * m + i].push_back(make_pair(0, j * m + i - m));
		}
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; //가중치가 낮은 것부터 뽑도록 우선순위 큐
	length[0] = 0; //나에서 나로 가는 최단경로는 0
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		int cost = q.top().first;
		int now = q.top().second;
		q.pop();
		if (length[now] < cost || visited[now]) continue;
		visited[now] = true;
		for (int i = 0; i < adj[now].size(); i++) {
			if (length[adj[now][i].second] > adj[now][i].first + cost) {
				q.push(make_pair(adj[now][i].first + cost, adj[now][i].second));
				length[adj[now][i].second] = adj[now][i].first + cost;
			}
		}
	}
	cout << length[n * m - 1];
	return 0;
}

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

문제

문제

출처

ICPC

1261 알고스팟 런타임에러 원인을 정말 모르겠습니다 도와주세요

hek0628 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말