글 읽기 - C++문제가 뭔지모르겠습니다.

ojh031 5년 전 0

DFS로 하다가 시간초과가 나길래

그 것만 살짝 메모이제이션을 써주었더니 제대로된 결과값이 안나오는데 이유를 모르겠습니다

#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;

int start[501][501]; //각 시작점
int arr[501][501];
int n;
int cnt = 0;
int dfs(int x, int y) { //경로를 찾는다. 메모이제이션만쓰면댐
	cnt++;
	if (start[x][y] != -1)
		return start[x][y]; //이미 방문
	start[x][y] = 1;
	if (arr[x][y] < arr[x + 1][y] && x + 1 <= n) { //현재점보다 목적지가 더 크다면
		return start[x][y] = max(dfs(x + 1, y) + 1, start[x][y]);
	}
	if (arr[x][y] < arr[x - 1][y] && x - 1>0) {
		return start[x][y] = max(dfs(x - 1, y) + 1, start[x][y]);
	}
	if (arr[x][y] < arr[x][y + 1] && y + 1 <= n) {
		return start[x][y] = max(dfs(x, y + 1) + 1, start[x][y]);
	}
	if (arr[x][y] < arr[x][y - 1] && y - 1>0) {
		return start[x][y] = max(dfs(x, y - 1) + 1, start[x][y]);
	}
	return start[x][y];
}

int main() {
	cin >> n;
	int m = -1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
			start[i][j] = -1; //시작점은 1day로 초기화
		}
	} //대나무의 양입력

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			m = max(dfs(i, j), m);
		}
	}
	cout << m << endl;
	cout << "cnt:" << cnt << endl;
	return 0;
}

djm03178 5년 전 0

한 방향만 더 많은 대나무가 있는 게 아니라면, 가능한 모든 방향을 다 가보고 그 중에 최댓값을 찾아야 합니다.

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

문제

문제

출처

ICPC

C++문제가 뭔지모르겠습니다.

ojh031 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말