글 읽기 - 1520번 질문 드립니다 ㅠㅠ

lsj5778 6년 전 0

1520번 질문이 있습니다 ㅜㅜ

DFS와 메모이제이션 개념에 대해서 처음 공부하느라

재귀의 구현이 너무 어려워서 이해가 잘 가지 않네요 ㅠㅠ

제 생각으로는 한번 지나 갔다고 기록된 길을 메모이제이션 한 후

나중에 메모이제이션 된 길을 만난 수만큼 경로가 있다고 생각을 해서 코드를 작성해봤습니다ㅜㅜ

도움 좀 주세요ㅠㅠ

#include <stdio.h>
#pragma warning(disable:4996)

int n, m, max = 1;//max는 경로의 수
int map[501][501], dp[501][501];
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int dfs(int y, int x){
	if (dp[y][x] != -1){//메모이제이션 된 구간을 만나면 경로의 갯수 1개 추가
		//printf("memo #%d\n", max);
		max++; 
		return dp[y][x];
	}
	dp[y][x] = 0;

	for (int i = 0; i < 4; i++){
		int xnew = x + dx[i];
		int ynew = y + dy[i];
		if (xnew <= m&&xnew >= 1 && ynew <= n && ynew >= 1){
			if (map[ynew][xnew] < map[y][x]){
				//printf("(%d %d)\n", ynew, xnew);
				dp[y][x]+=dfs(ynew, xnew);
			}
		}
	}
	return dp[y][x];
}

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			scanf("%d", &map[i][j]);
			dp[i][j] = -1;
		}
	}
	dfs(1, 1);
	printf("%d\n", max);
	return 0;
}

mokiia 6년 전 0

반례데이터 하나 드리고 갑니다

3 3
9 4 3
8 5 2
7 6 1

일 때,

9 4 3 2 1

9 8 5 2 1

9 8 7 6 1

9 8 5 4 3 2 1

9 8 7 6 5 4 3 2 1

9 8 7 6 5 2 1

정답이 6이 되어야합니다.

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

문제

문제

출처

ICPC

1520번 질문 드립니다 ㅠㅠ

lsj5778 6년 전 0

mokiia 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말