글 읽기 - 틀린 케이스를 찾아주세요(57%에서 계속 틀립니다 ㅠㅠ)

jupiny 6년 전 0

벽을 만났을 때 가중치 1을 추가하는 방식으로 다익스트라 알고리즘을 사용하였습니다.

우선순위큐(min_heap)을 사용하였고, <누적된 가중치, 현재 위치>를 item으로 push, pop 하고 있습니다.

마지막 도착점의 누적된 가중치가 2 미만일 시에는, 벽 1 이하를 통과하여 도착한 경우이므로 지나온 경로를 재귀함수로 추적하여 카운트하였습니다.

본 문제의 테스트 케이스는 물론, 질문 답변들에 나와있는 모든 테스트 케이스를 돌렸을 때는 잘 통과하였지만, 57%에서 계속 틀리네요ㅠㅠ
고수님들의 많은 도움 부탁드립니다.

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

int n, m;
vector<string> board;
vector<string> trace;
vector<vector<int> > cost;
// 오른, 왼, 아래, 위
const int dy[] = {0, 0, 1, -1};
const int dx[] = {1, -1, 0, 0};
const char moves[] = {'L', 'R', 'U', 'D'};
const int INF = 987654321;

int find_length(int cur_y, int cur_x) {
	if(cur_y == 0 && cur_x == 0)
		return 1;
	if(trace[cur_y][cur_x] == 'L') {
		return 1 + find_length(cur_y, cur_x-1);
	}
	else if(trace[cur_y][cur_x] == 'R') {
		return 1 + find_length(cur_y, cur_x+1);
	}
	else if(trace[cur_y][cur_x] == 'U') {
			return 1 + find_length(cur_y-1, cur_x);
		}
	else {
		return 1 + find_length(cur_y+1, cur_x);
	}
}

int main() {
	cin >> n >> m;
	cost.resize(n, vector<int>(m, INF));
	trace.resize(n, string(m, ' '));

	for(int i=0; i<n; i++) {
		string s;
		cin >> s;
		board.push_back(s);
	}

	// pair<cost, position>
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.push(make_pair(0, 0));
	cost[0][0] = 0;
	while(true) {
		pair<int, int> front = pq.top();
		int cur_cost = front.first;
		int cur = front.second;
		int cur_y = cur/m;
		int cur_x = cur%m;
		pq.pop();

		if(cur == (n*m-1))
			break;

		for(int i=0; i<4; i++) {
			int next_y = cur_y + dy[i];
			int next_x = cur_x + dx[i];
			if(next_y >= 0 && next_y < n && next_x >= 0 && next_x < m && cost[next_y][next_x] != -1) {
				int next_cost;
				if(board[next_y][next_x] == '1') {
					next_cost = cur_cost + 1;
				}
				else {
					next_cost = cur_cost;
				}
				if(next_cost < cost[next_y][next_x]) {
					cost[next_y][next_x] = next_cost;
					trace[next_y][next_x] = moves[i];
					pq.push(make_pair(next_cost, next_y*m + next_x));
				}
			}
		}
		cost[cur_y][cur_x] = -1;
	}
    
	int ret = -1;
	if(cost[n-1][m-1] < 2) {
		ret = find_length(n-1, m-1);
	}
	cout << ret << endl;
	return 0;
}

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

문제

문제

출처

ICPC

틀린 케이스를 찾아주세요(57%에서 계속 틀립니다 ㅠㅠ)

jupiny 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말