글 읽기 - 이 문제 어떻게 접근하셨는지 궁금합니다.

joyyir 8년 전 0

안녕하세요?
저는 이 문제를 되추적 기법으로 접근했는데 시간 초과 에러가 발생했습니다.
모든 경로를 탐색하면서 연료 범위를 넘어서는 경로는 제외시키는 방법을 썼는데 아무래도 비효율적인 것 같습니다.
알고리즘 강의만 듣다가 실제로 적용시켜보려니 만만치 않네요...
어떻게 이 문제를 접근하셨는지 실마리라도 알려주시면 감사하겠습니다.

#include <cstdio>
#include <stack>
#define RIGHT		0
#define DOWN		1
#define INFINITE	999999
using namespace std;

int T;
int M, N, L, G;
int rowArr[100][100], colArr[100][100];
int minTurn, beforeDir;
stack<int> st;

void checkNode(int x, int y, int nowCost, int turnCnt){
	if(nowCost <= G){ // promising 조건 (연료 범위 내에 갈 수 있는가?)
		if(x == M-1 && y == N-1){ // solution 조건 (종점에 도착하였는가?)
			if(turnCnt < minTurn)
				minTurn = turnCnt;
		}
		else{ // solution이 아닐 경우, 각 child를 검사함
			if(y + 1 < N){ // 오른쪽으로 이동
				if(!st.empty()) beforeDir = st.top();
				st.push(RIGHT);
				if(st.size() == 1 || beforeDir == RIGHT) // 방향 전환이 있는지 판별
					checkNode(x, y+1, nowCost+rowArr[x][y], turnCnt);
				else
					checkNode(x, y+1, nowCost+rowArr[x][y], turnCnt+1);
			}
			if(x + 1 < M){ // 아래로 이동
				if(!st.empty()) beforeDir = st.top();
				st.push(DOWN);

				if(st.size() == 1 || beforeDir == DOWN) // 방향 전환이 있는지 판별
					checkNode(x+1, y, nowCost+colArr[x][y], turnCnt);
				else
					checkNode(x+1, y, nowCost+colArr[x][y], turnCnt+1);
			}
		}

		if(!st.empty()) st.pop();
	}
	else{
		if(!st.empty()) st.pop();
	}
}

int main(){
	scanf("%d", &T);

	while(T--){
		// 사용자 입력
		scanf("%d %d %d %d", &M, &N, &L, &G);
		for(int i = 0; i < M; i++) for(int j = 0; j < N-1; j++) scanf("%d", &rowArr[i][j]);
		for(int i = 0; i < M-1; i++) for(int j = 0; j < N; j++) scanf("%d", &colArr[i][j]);

		// 연산
		minTurn = INFINITE;
		checkNode(0, 0, 0, 0);

		// 결과 출력
		printf("%d\n", (minTurn == INFINITE) ? (-1) : (minTurn + L*(M+N-2)) );
	}

	return 0;
}

hihihi 8년 전 3

다이나믹으로 풀었습니당

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

문제

문제

출처

ICPC

이 문제 어떻게 접근하셨는지 궁금합니다.

joyyir 8년 전 0

hihihi 8년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말