[BOJ] 1103 게임 - python

1103번: 게임

1103번: 게임

import sys

sys.setrecursionlimit(10**6) #python3는 10**6까지 , pypy3는 10**5까지 / 아니면 메모리초과
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split(" "))
B = [list(input()) for _ in range(N)]
#print(B)
visited = [[False]*M for _ in range(N)] #한 루트에서 사이클이 형성됐는지를 체크하는 변수
dp = [[0]*M for _ in range(N)] # dp테이블 사용 가능

#맨처음은 0,0에서 시작
dir = [[-1,0],[1,0],[0,-1],[0,1]] #위,아래,왼,오

def dfs(a,b):

    #종료조건
    if (0 > a or a > N - 1) or (0 > b or b > M - 1): 
		#범위를 벗어날 수 있는 조건 검사는 항상 맨 처음에
        return 0
    if visited[a][b] == True: # 사이클을 형성할 경우
        print(-1)
        exit()
    if B[a][b] == "H":
        return 0

		#이미 방문했었으면 다시 계산하지 않고 바로 max값 리턴
    if dp[a][b] != 0: 
        return dp[a][b]

    visited[a][b] = True #사이클 검사 위한 변수 설정
    #갱신
    for d in dir:
        dp[a][b] = max(dp[a][b] , dfs(a + d[0] * int(B[a][b]), b + d[1] * int(B[a][b])) + 1)
    visited[a][b] = False #한 루트에서 사이클 다 돔

    return dp[a][b] #가지에서 루트까지 다 돌았을 때

print(dfs(0,0))
#모든 애들의 return이 끝났을 때

얻어가는 것

• DP 한 route에서 사이클을 형성하는지 확인하기

visited = [[False]*m for _ in range(N)]#방문확인 변수

def dfs(n):
	#종료조건
	#dp테이블존재
	**#사이클 형성 확인**
	**if visited[a][b] == True:**
		#해당하는 행동 작성

	**visited[a][b] = True #일단 방문했음**
	#가지치기
	for i in range(..):
		dp[n] = 어쩌구저쩌구
	**visited[a][b] = False** #해당 루트노드까지 도달했으니 다른 루트로 가야지, false로
	return dp[n] #루트노드 도달

• 범위를 벗어나는 것을 확인하는 조건 검사는 항상 첫 빠따로

def function(a,b):
	if (a < 0 or a > N-1) or (b < 0 or b > N-1):
		어쩌구저쩌구
	if visited[a][b]:
		#이걸 먼저해버리면 인덱스 접근 오류 발생

• 재귀함수 sys.setrecursionlimit

#python3
sys.setrecursionlimit(10**6)

#pypy3
sys.setrecursionlimit(10**5)

#왜인지는 모르겠는데 이렇게 안하면 메모리초과 뜸..

느낀점

"211005"

소요 시간 : 3H

• dp + dfs를 다시 학습할 수 있는 시간이었다.
• 어떻게 빠져나가고 return하면 뭐가 되고 하는거를 연습을 통해 감을 익혀야겠다
• 근데 아직 왜 dp테이블을 사용해야하는지 이유는 잘 모르겠다
• setresursionlimit은 재귀에 필수다.
• python3하고 pypy3하고 다른거 빡친다 (뭐 메모리가 작은지 어떻게 알아 알려줘야지!!)