1103. 게임
12330 단어 백트래킹다이나믹 프로그래밍다이나믹 프로그래밍
문제 링크
문제 코드
num_list = list(map(int,input().split()))
row = num_list[0]
col = num_list[1]
maze = [[0 for i in range(col)]for j in range(row)]
visited = [[0 for i in range(col)]for j in range(row)]
cycle = [[0 for i in range(col)]for j in range(row)]
for i in range(row):
tmp = input()
for j in range(col):
maze[i][j] = tmp[j]
max_count = 0
def back_tracking(x,y,count):
global row
global col
global max_count
if max_count == float('INF'):
return
visited[x][y] = count
max_count = max(max_count,count)
move_len = int(maze[x][y])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(4):
next_x = x+(dx[i]*move_len)
next_y = y+(dy[i]*move_len)
if 0<=next_x<row and 0<= next_y <col and maze[next_x][next_y] !='H':
if cycle[next_x][next_y] == 1:
max_count = float('INF')
return
elif visited[next_x][next_y] == 0 or visited[next_x][next_y] < count+1:
cycle[next_x][next_y] = 1
back_tracking(next_x,next_y,count+1)
cycle[next_x][next_y] = 0
else :
if count > max_count:
max_count = count
visited[0][0] = 1
back_tracking(0,0,1)
if max_count != float('INF'):
print(max_count)
else:
print(-1)
문제 풀이
- 기존의 그래프 문제와 다르게, visited와 cycle 두개의 확인 지표가 필요하다.
- 처음에는 기존의 maze 문제처럼 BFS로 풀려고했다.
- 왔던 타일을 다시 오는 경우가 발생할 수 있기 때문에 BFS로 풀 수 없다는 것을 알게되었다.
- DFS로 변경했더니, visited를 설정해 줄 수 없어서 recursion 횟수가 급증했다.
- visited 배열을 DP로 활용하고, 무한번 왔다갔다 하는것을 체크하기 위한 cycle 배열을 추가했다.
- visited에는 기본적으로 지금까지의 count가 들어간다.
- 프루닝을 할때 다음 구슬의 위치가 현재 count+1보다 크면 이미 더 좋은 방법으로 거길 지나간 것으로 판단해서 프루닝을 해준다.
- 추가적인 프루닝으로 맥스 카운트가 이미 inf이면 그 후의 계산이 의미없으므로 바로 return하도록 했다.
- 1등 코드도 거의 유사함
Author And Source
이 문제에 관하여(1103. 게임), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youngjin_kim2/1103.-게임저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)