글 읽기 - 1890 점프 질문입니다

jh1125kr 8년 전 0

스택을 이용하여 미로찾기 문제 형식으로 풀었습니다

구조체 사용하여 처음에 east(오른쪽), south(아래)를 1로 선언하고 distance에는 현재점에서 갈수있는 거리를 넣어줬습니다.

방문하면 0으로 고쳐줬습니다. 그리고 조건에 부합하면(현재점에서 갈수있는 거리+현재 index가 n-1의 배열 범위를 벗어나지 않으면)

스택에 넣어줬습니다.

몇개의 테스트 케이스를 해보아도 다 맞는것 같은데 어디서 틀렸는지 모르겠습니다..ㅠㅠ

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
typedef struct 
{
	int r,c;
	int east;
	int south;
	int distance;
} element;
void element_init(element *e)
{
	e->r=e->c=0;
	e->east=e->south=1;
	e->distance=0;
}
element maze[100][100];
stack<element> s;
int n;
long long int ans=0;

void push_loc(int r, int c)
{
	element *ee=&(s.top());
	int row,col,dis;
	row=ee->r;
	col=ee->c;
	dis=ee->distance;

	if(row==n-1 && col==n-1)
	{
		ans++;
		s.pop();
		return;
	}
	if(ee->east!=0)
	{
		if(col+dis<n)
		{
			ee->east=0;
			s.push(maze[r][c+dis]);
			push_loc(r,c+dis);
		}
		else
			ee->east=0;
	}
	if(ee->south!=0)
	{
		if(row+dis<n)
		{
			ee->south=0;
			s.push(maze[r+dis][c]);
			push_loc(r+dis,c);
		}
		else
			ee->south=0;
	}
	if(ee->east==0 && ee->south==0)
	{
		if(s.size()!=1)
		{
			s.pop();
			push_loc(s.top().r,s.top().c);
			return;
		}
		else
			return;
	}
}


int main()
{
	int tmp=0;
	int i=0, j=0;
	for(i=0; i<10; i++)
	{
		for(j=0; j<10; j++)
			element_init(&maze[i][j]);
	}
	cin>>n;
	for(i=0; i<n; i++)
	{
		for(j=0; j<n; j++)
		{
			cin>>tmp;
			maze[i][j].distance=tmp;
			maze[i][j].r=i;
			maze[i][j].c=j;
		}
	}
	int r,c,dis;
	s.push(maze[0][0]);
	do
	{
		r=s.top().r;
		c=s.top().c;
		dis=s.top().distance;
		if(c+dis>=n && r+dis>=n)
			s.pop();
		else
		{
			if(c+dis<n && s.top().east!=0)
			{
				s.top().east=0;
				s.push(maze[r][c+dis]);
				push_loc(r,c+dis);
			}
			else if(r+dis<n && s.top().south!=0)
			{
				s.top().south=0;
				s.push(maze[r+dis][c]);
				push_loc(r+dis,c);
			}
			if(s.top().east==0 && s.top().south==0)
				s.pop();
		}
	}while(!s.empty());
	cout<<ans<<endl;
}

yukariko 8년 전 1

이 소스는 한 번 방문하고 나면 그쪽으론 다시 안가게 끔 구현된것 같은데

그렇게 하려면 그 방향으로 방문했을때의 정답을 계산을 하고, 다음 다시 그쪽을 방문시 계산한 값을 내놓는

흔히 말하는 dp 형식을 띄고 있어야 합니다.

이 소스는 그냥 n-1, n-1에 도착하면 ans 값을 1씩 증가하는것이라

답이 틀리게 됩니다.

맞다고 해도 답이 2^63 근처까지 갈 수 있기 때문에 시간초과를 받게될 것 같군요..

dp와 재귀를 사용하면 간단하게 풀 수 있는 문제입니다.

jh1125kr 8년 전 0

아 그렇군요...ㅠㅠ답변 감사합니다 dp로 다시풀어야겠네요ㅠㅠ

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

문제

문제

출처

ICPC

1890 점프 질문입니다

jh1125kr 8년 전 0

yukariko 8년 전 1

jh1125kr 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말