120. 게임

백준

1. Python

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n, m = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(n)]
 
visited = [[False]*m for _ in range(n)] #방문 여부

dp = [[0]*m for _ in range(n)]

result = 0
def dfs(x, y, cnt):
    global result
    result = max(result, cnt) #최대 횟수기 때문
    for i in range(4):
        nx = x + int(arr[x][y]) * dx[i] #고른 방향으로 x만큼 이동
        ny = y + int(arr[x][y]) * dy[i]
        
        #바깥으로 나가지 않고, 구멍 x, 이전 보다 움직이 횟수가 많다면 진행
        if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] != "H" and cnt + 1 > dp[nx][ny]:
            if visited[nx][ny]:
                print(-1)
                exit()
            else:
                dp[nx][ny] = cnt + 1 
                visited[nx][ny] = True
                dfs(nx, ny, cnt + 1)
                visited[nx][ny] = False
 
dfs(0, 0, 0)
print(result + 1) #마지막 자표에서 바깥으로 빠지거나 구멍에 빠져도 되기에  +1

2. C++

#include <iostream> 
using namespace std; 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

int N, M; 
char map[52][52]; 
bool visited[52][52]; //사이클 확인 위해 
int dp[52][52]; 

int dy[4] = {-1, 0, 1, 0}; 
int dx[4] = {0, -1, 0, 1};

int solve(int y, int x){

    if(y < 1 || y > N || x < 1 || x > M || map[y][x] == 'H'){
    
    	return 0; 
    } 
    
    if(visited[y][x] == true){
		printf("-1\n"); 
        exit(0); 
        
    } 
    
    if(dp[y][x] != -1){
    
    	return dp[y][x]; 
        
    }
    
    dp[y][x] = 0;

	visited[y][x] = true;
	int step = map[y][x]-'0'; 
    for(int i=0; i<4; ++i){
		int ny = y + (dy[i] * step); 
        int nx = x + (dx[i] * step); 
        dp[y][x] = max(dp[y][x], solve(ny, nx)+1); 
        
}


int main(){ 

    memset(visited, false, sizeof(visited));
	memset(dp, -1, sizeof(dp)); 
    scanf("%d%d", &N, &M);
	
    for(int i=1; i<=N; ++i){ 
    	char str[52]; 
        scanf("%s", str); 
        
        for(int j=1; j<=M; ++j){ 
        	map[i][j] = str[j-1]; 
        } 
    }
    
    int result = solve(1, 1); 
    printf("%d\n", result);
    
    return 0;
    
}

#include <cstdio>

int n, m, ans, dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1}, limit;
int max_count[50][50];  // 시작부터 가장 많이 점프 한 횟수 
char board[50][51];

void dfs(int y, int x, int cnt) {
    if (ans < cnt) ans = cnt;
    if (ans > limit) return;
    // 예외 처리
    if (y < 0 || n <= y || x < 0 || m <= x || board[y][x] == -1) return; 
    if (cnt <= max_count[y][x]) return;
    max_count[y][x] = cnt;
    int mul = board[y][x];
    for (int i = 0 ; i < 4 ; i++) {
        dfs(y + dy[i] * mul, x + dx[i] * mul, cnt + 1);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    limit = n * m;
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < m ; j++) {
            // 처음 시작 점프 횟수가 0일 예정이라서 0보다 작은 -1로 초기화를 했는데,
            // 다른 방식으로도 구현이 가능합니다. 
            max_count[i][j] = -1;
        }
    }
    for (int i = 0 ; i < n ; i++) {
        scanf("%s", board[i]);
        for (int j = 0 ; j < m ; j++) {
            if (board[i][j] == 'H') board[i][j] = -1;
            else board[i][j] -= '0';
        }
    }
    dfs(0, 0, 0);
    if (ans > limit) ans = -1;
    printf("%d", ans); 
}