[dfs/백준] 1103번 : 게임

- 문제 : https://www.acmicpc.net/problem/1103

 

Gold Level 2 문제

 

풀이 로직

1. 현재 위치의 값에 따라서 점프를 뛴다

2. 도착한 위치가 보드 밖이거나 'H'일 때 게임이 끝나야 한다 

3. 무한 반복인 경우 -1 출력 (재방문한 좌표가 있을 때이므로, visit 행렬을 이용한다)

 

+ 시간초과가 나지 않기 위해서 dp 행렬 이용(dp 행렬 이용하는게 쉽지 않다)

 

- 정답 풀이 :

import sys
sys.setrecursionlimit(10 ** 6)

n,m = map(int,input().split())
data = [list(input()) for _ in range(n)]
visit = [[0]*m for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]

answer = 0
dp = [[0]*m for _ in range(n)]
def dfs(x,y,count):
    global answer
    visit[x][y] = 1
    answer = max(answer,count)    
    for i in range(4):
        nx,ny = x + int(data[x][y]) * dx[i], y + int(data[x][y]) * dy[i]
        if 0 <= nx < n and 0 <= ny < m and data[nx][ny] != "H" :
            #여기
            if count + 1 > dp[nx][ny]:
                #여기
                if visit[nx][ny]:
                    print(-1)
                    exit()
                else:
                    #여기
                    dp[nx][ny] += 1
                    visit[nx][ny] = 1
                    dfs(nx,ny,count + 1)
                    #여기
                    visit[nx][ny] = 0 
                
dfs(0,0,0)
print(answer + 1)

 

- 시도한 풀이 :

이렇게 하면 recursionerror가 발생한다

import sys
sys.setrecursionlimit(10 ** 3)

n,m = map(int,input().split())
data = [list(input()) for _ in range(n)]

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

count = 0
def dfs(x,y):
    global count
    for i in range(4):
        nx,ny = x + int(data[x][y]) * dx[i], y + int(data[x][y]) * dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if data[nx][ny] != "H":
                count += 1
                dfs(nx,ny)
dfs(0,0)

if count > 10 ** 3 :
    print(-1)
else: 
    print(count)