글 읽기 - 런타임에러가 나옵니다. 그리고 DP굳이써야하는 이유가 궁금합니다.

isvara 4년 전 0

우선 각 정점당 한번씩 만방문하도록하고 두번째에 방문한다면 cycle이 존재한다는 것이고 가장 큰 값 INF를 리턴시켜서 값을 구하도록 풀어봤습니다.

그리고 제출하니 런타임 에러가 나옵니다.

그리고 여러 질문을 보니까 DP를 쓰던데

애초에 중복으로 방문이 되는 경우는 무조건 싸이클이 있는 것이니 무한대로 움직일 수 있는거고 바로 종료가 될텐데

한번식만 방문해서 O(NM)으로 풀리지않나요?

그러니 굳이 DP로 처리안하고 풀어도 시간초과가 날 일이 있나요ㅜ?

이유점 설명해주십쇼 그리구 코드지적도 부탁드립니다.

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
using namespace std;

int dx[4] = { 0,-1,1,0 };
int dy[4] = { -1,0,0,1 };
const int INF = 987654321;
int N, M;
string map[51];
bool visited[51][51];

int DFS(int y , int x)//x,y부터 시작해서 이동가능한 최대 값을 반환
{
	int ret = 1;

	visited[y][x] = true;
	
	if (map[y][x] == 'H')//정확히 그지점이 구멍일경우 바로 종료
		return 0;

	for (int i = 0; i < 4; i++)
	{
		int nx = x+(map[y][x]-'0')* dx[i];
		int ny = y+(map[y][x]-'0')* dy[i];
		
		if (nx >= 0 && ny >= 0 && nx < M && ny < N)
		{
			if (visited[ny][nx])//재방문이 됬다면 cycle존재=>무한번 움직일 수 있다
				return INF;
			else
				ret = max(ret, 1 + DFS(ny, nx));
		}
	}
	return ret;
}
int main()
{
	int res ;
	memset(visited, false, sizeof(visited));
	memset(map, 0, sizeof(map));

	cin >> N >> M;
	
	for (int i = 0; i < N; i++)
		cin >> map[i];
	res=DFS(0, 0);

	if (res >= INF)
		cout << -1;
	else
		cout << res;
	return 0;
}

djm03178 4년 전 1

런타임 에러는 43번째 줄 때문에 납니다. 객체의 배열은 함부로 memset과 같은 기초 메모리 함수를 사용해서 초기화를 하면 안 됩니다. 그 줄만 지우면 런타임 에러는 사라집니다.

그리고 이렇게 하면 안 되는 이유는, visited를 한 번 체크한 뒤 그 이후로 더 진행해서 원래 자리로 돌아오는 것이 아닌, 그보다 이전에 있던 칸에서 다른 경로를 통해 이 자리로 다시 돌아오는 경우도 있을 수 있고 이 때는 사이클이 아니기 때문입니다.

isvara 4년 전 0

감사합니다. 탐색을 하는 도중에 다른 정점에서 visited로 체크됐던 정점을 다시가는 경우가 있었군요 ㅜ

섣부르게 생각한것같습니다. ㅜ ㅜ dp로 다시풀어봐야겠어요

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

문제

문제

출처

ICPC

런타임에러가 나옵니다. 그리고 DP굳이써야하는 이유가 궁금합니다.

isvara 4년 전 0

djm03178 4년 전 1

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말