글 읽기 - 반레를 알고 싶습니다.

adfsfsf 5년 전 0

DFS를 이용했으며, visit배열을 통해 현재 루트에서 지나온 칸들을 체크하였고, 이미 지나온 칸을 다시 방문하면 루프 처리를 해 재귀를 전부 빠져나간 후 -1을 출력합니다.(루프가 있다는 말은 무한히 반복할 수 있다는 의미이므로)

현재 방문한 칸이 'H' 또는 마지막 칸(무조건 보드 밖으로 나가는 칸)이면 dp에 다음 칸이 없다는 표시를 한 후, 해당 칸에 몇 번의 이동만에 도달했는지를 저장합니다.

만약 dp에 값이 이미 채워진 칸에 들어섰다면 dp에 있는 값이 현재 해당 칸까지 오는 데까지 걸린 횟수보다 많거나 같은가를 확인합니다. 많거나 같다면 무조건 루프가 아닙니다. 이 때는 이 루트 끝까지 걸리는 횟수를 현재 횟수에 추가해서 반환합니다.

dp에 있는 값이 더 적다면 루프일 수 있으므로 체크합니다. 루프이면 루프 체크용 전역 변수를 true로 바꾼 후 함수를 빠져나갑니다. 루프가 아니라면 현재 값과 기존 dp값의 차이를 구한 후 루트를 따라가면서 그 차이만큼 dp값을 다 더해줍니다. 그 후, 변경된 루트의 최종값을 반환합니다.

위의 경우들이 아니면 dp에 값을 채워야 합니다. 우선, 현재 칸까지의 횟수를 넣습니다. 그리고, 다음 좌표를 구해야 합니다. 다음 좌표는 4가지 방향을 차례대로 확인하며, 가장 큰 값을 반환하는 방향의 칸을 dp에 넣습니다.

#include <iostream>
#include <string>
using namespace std;
struct queue {
	int a = -1, b = -1;
};
struct queue2 {
	int a = -2, b = -2, c = -2;//a와 b는 좌표, c는 값
};
int dfs(string *s, queue a, int n);
queue2 **dp;
bool **visit;
int n, m;
bool loop = false;
int main(void)
{
	int i, j, max = 0, a = 0;
	bool check;
	string *s;
	queue al;
	cin >> n >> m;
	s = new string[n];
	dp = new queue2 *[n];
	visit = new bool *[n];
	for (i = 0; i < n; i++)
	{
		while(s[i].compare("") == 0)
			getline(cin, s[i]);
		dp[i] = new queue2[m];
		visit[i] = new bool[m];
	}
	al.a = 0;
	al.b = 0;
	dfs(s, al, 0);
	//dp에서 끝까지 진행한다. 그 후, 마지막 칸이 구멍이면 c값을, 루프가 있을 경우 -1을, 이외에는c+1을 출력한다.
	if (loop)
	{
		cout << -1 << endl;
		return 0;
	}
	while (dp[al.a][al.b].a != -1)
	{
		i = dp[al.a][al.b].a;
		j = dp[al.a][al.b].b;
		al.a = i;
		al.b = j;
	}
	if (s[al.a][al.b] == 'H')
		cout << dp[al.a][al.b].c << endl;
	else
		cout << dp[al.a][al.b].c + 1 << endl;
	return 0;
}
int dfs(string *s, queue a, int n1)//s는 미로 전체를, dp는 각 칸의 정보를, a는 현재 위치한 칸, n은 현재 칸이 몇 번째 칸인지를 의미한다.
{
	int al, c, aa, bb, nn = -1, nn1 = -1;
	queue b;
	visit[a.a][a.b] = true;
	if (loop)//루프가 있다면 바로 종료한다.
	{
		visit[a.a][a.b] = false;
		return -3;
	}
	if (s[a.a][a.b] == 'H')//현재 칸이 구멍이라면 dp에서 다음 칸은 없음으로 처리(-1, -1)
	{
		dp[a.a][a.b].a = -1;
		dp[a.a][a.b].b = -1;
		dp[a.a][a.b].c = dp[a.a][a.b].c > n1 ? dp[a.a][a.b].c : n1;
		visit[a.a][a.b] = false;
		return n1;
	}
	al = s[a.a][a.b] - '0';
	if ((a.a + al) >= n && (a.b + al) >= m && (a.a - al) < 0 && (a.b - al) < 0)//다음 칸이 없으면 dp에서 다음 칸은 없음으로 처리(-1, -1)
	{
		dp[a.a][a.b].a = -1;
		dp[a.a][a.b].b = -1;
		dp[a.a][a.b].c = dp[a.a][a.b].c > n1 ? dp[a.a][a.b].c : n1;
		visit[a.a][a.b] = false;
		return n1 + 1;
	}
	if (dp[a.a][a.b].c >= 0)//현재 칸이 이미 점검한 칸이라면 dp의 c 값과 n1을 비교
	{
		if (dp[a.a][a.b].c >= n1)//dp의 c값이 n1과 같거나 n1보다 크다면 최댓값 찾아서 반환
		{
			b.a = a.a;
			b.b = a.b;
			while (true)
			{
				aa = dp[b.a][b.b].a;
				bb = dp[b.a][b.b].b;
				if (aa == -1 || aa == -2)
					break;
				b.a = aa;
				b.b = bb;
			}
			visit[a.a][a.b] = false;
			return (dp[b.a][b.b].c - dp[a.a][a.b].c + n1);
		}
		else//dp의 c값이 n1보다 작다면
		{
			if (visit[a.a][a.b] == true)//중간에 루프가 나오면 루프를 체크한 후 종료
			{
				loop = true;
				return -3;
			}
			b.a = a.a;
			b.b = a.b;
			c = n1 - dp[a.a][a.b].c;//n1-c의 값을 구한다.
			while (b.a != -2 && b.a != -1)//그 후 dp를 따라가면서 이후 루트의 c 값을 증가시킨다.
			{
				dp[b.a][b.b].c += c;
				aa = dp[b.a][b.b].a;
				bb = dp[b.a][b.b].b;
				b.a = aa;
				b.b = bb;				
			}
			visit[a.a][a.b] = false;
			return  dp[b.a][b.b].c;//다 끝난 후 최댓값을 반환한다.
		}
	}			
	dp[a.a][a.b].c = n1;//현재 칸의 dp의 c 값을 n1으로 처리한다.
	//다음 칸들을 탐색한다.
	b.a = a.a + al;
	b.b = a.b;
	if (b.a < n)
	{
		nn1 = dfs(s, b, n1 + 1);
		if (nn1 == -3)//루프가 발견된 경우
			return -3;
		if (nn < nn1)
		{
			dp[a.a][a.b].a = b.a;
			dp[a.a][a.b].b = b.b;
			nn = nn1;
		}
	}
	b.a = a.a;
	b.b = a.b + al;
	if (b.b < m)
	{
		nn1 = dfs(s, b, n1 + 1);
		if (nn1 == -3)//루프가 발견된 경우
			return -3;
		if (nn < nn1)
		{
			dp[a.a][a.b].a = b.a;
			dp[a.a][a.b].b = b.b;
			nn = nn1;
		}
	}
	b.a = a.a - al;
	b.b = a.b;
	if (b.a >= 0)
	{
		nn1 = dfs(s, b, n1 + 1);
		if (nn1 == -3)//루프가 발견된 경우
			return -3;
		if (nn < nn1)
		{
			dp[a.a][a.b].a = b.a;
			dp[a.a][a.b].b = b.b;
			nn = nn1;
		}
	}
	b.a = a.a;
	b.b = a.b - al;
	if (b.b >= 0)
	{
		nn1 = dfs(s, b, n1 + 1);
		if (nn1 == -3)//루프가 발견된 경우
			return -3;
		if (nn < nn1)
		{
			dp[a.a][a.b].a = b.a;
			dp[a.a][a.b].b = b.b;
			nn = nn1;
		}
	}
	visit[a.a][a.b] = false;
	return nn;
}

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

문제

문제

출처

ICPC

반레를 알고 싶습니다.

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말