문제 출처: https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/woodstick-fraud/description
import heapq
routes = [
[ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0], #22개
[ 0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40, 0], #14개
[ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40, 0], #18개
[ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40, 0], #24개
]
tp = [(0, 5), (0, 10), (0, 15)] # 도달하면 i + 1번째 route로 이동
same_spot = [
[(1, 9), (2, 13), (3, 19)], #25
[(1, 10), (2, 14), (3, 20)], #30
[(1, 11), (2, 15), (3, 21)], #35
[(0, 20), (1, 12), (2, 16), (3, 22)], #40
] #같은 그룹은 동일 지점
finish = [(0, 21), (1, 13), (2, 17), (3, 23)] #도착
# 말의 상태
positions = [(0,0) for _ in range(4)]
nums = []
def isOccupied(i, j):
if (i, j) in finish: #도착한 말
print("finished horse")
return False
if (i, j) in positions:
print(i, j, "occupied")
return True
for g in same_spot:
if((i, j) in g):
for horse in positions:
if horse in g:
print(i,j,"occupied")
return True
print(i,j,"not occupied")
return False
rets = []
def dfs(cp, cnt, idx, sum):
print(cp, cnt, idx, sum)
# 이동 가능이 보장됨.
# 점수 획득 - 현재는 cnt 반영
ci, cj = cp[idx]
cj = min(len(routes[ci]) - 1, cj + nums[cnt])
# 교차점이라면 route 이동
if (ci, cj) in tp:
ci = cj // 5
cp[idx] = (ci, cj) #말 위치 갱신
print(nums[cnt],"칸 앞으로,",routes[ci][cj],'점 획득')
print("갱신된 위치:",ci,cj,'\n')
sum = sum + routes[ci][cj]
if(cnt == len(nums) - 1):
heapq.heappush(rets, -sum)
print('push',sum)
return
for i in range(4):
# 1. 이동 가능한 말인지 확인하기
print('target horse:',cp[i])
ni, nj = cp[i]
if (ni, nj) in finish:
continue
# 2. 도착 가능 지점인지 확인하기
nj = min(len(routes[ni]) - 1, nj + nums[cnt + 1])
# 말이 존재하면 패스
if(isOccupied(ni, nj)):
continue
# 3. dfs 진행
dfs(cp, cnt + 1, i, sum)
nums = list(map(int, input().split()))
dfs(positions, 0, 0, 0)
print(-rets[0])여러 실수가 많지만 가장 큰건 dfs에서 cp 인자가 이전 노드로 돌아갈 때 상태가 원상복구가 되지 않는다. 따라서 재귀함수 호출 시 바뀌는 상태를 인자에 전달하고, 끝난 후 복구 로직을 넣어야 한다.
튜플의 배열로 선언하는 바람에 인자 전달할 때도 deep-copy를 해야 하는데, 그냥 장기판부터 일차원 배열로 하고 말 위치는 int배열로 하는게 좋다.
1차 수정 버전
import heapq
M = [
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, #20개 #38(19th) -> 40(32th)
# 이동 시작할 때, 10(5th) -> 13(20th), 20(10th) -> 22(23th), 30(15th) -> 28(25th)
13, 16, 19, # 19(22th) -> 25(28th)
22, 24, # 24(24th) -> 25(28th)
28, 27, 26, # 26(27th) -> 25(28th)
25, 30, 35, # 35(31th) -> 40(32th)
40, 0,
]
def isFinished(pos):
return pos == len(M) - 1
def go(pos, is_blue):
if(isFinished(pos)):
return pos
if(is_blue):
if(pos == 5):
return 20
elif(pos == 10):
return 23
else:
return 25
elif(pos == 19 or pos == 31):
return 32
elif(pos == 22 or pos == 24):
return 28
else:
return pos + 1
def isBlue(pos):
return pos == 5 or pos == 10 or pos == 15
def goN(pos, n):
if(isFinished(pos)):
return pos
i = 0
while(i < n):
is_blue = isBlue(pos) if i == 0 else False
pos = go(pos, is_blue)
i += 1
return pos
nums = []
sums = [] # 최대 힙
def dfs(pos, count, sum):
if(count == 10):
heapq.heappush(sums, -sum)
return
for i in range(4):
# 이전 말이 출발 안했으면 패스 (최적화)
if(i > 1 and pos[i - 1] == 0):
continue
# 출발 가능한 말인지 확인
if(isFinished(pos[i])):
continue
# 도착 가능한 지점인지 확인
np = goN(pos[i], nums[count])
if(np in pos):
return
# 현재 상태 저장
temp = pos[:]
# DFS 수행 후 상태 복구
pos[i] = np
dfs(pos, count + 1, sum + M[np])
pos = temp
nums = list(map(int, input().split()))
dfs([0,0,0,0], 0, 0)
print(-sums[0])실수 1
# 도착 가능한 지점인지 확인
np = goN(pos[i], nums[count])
if(np in pos):
return이 부분 실수로 return이라고 작성했다.
return하면 다음 재귀 실행 안하고 아예 종료해버리니 주의하기.
실수 2
np in pos 자체가 문제인게, 도착 지점은 중복 가능하므로 로직이 틀렸다.
# 도착 가능한 지점인지 확인
np = goN(pos[i], nums[count])
if(not isFinished(np) and np in pos):
continue로 수정.
실수 3(중요)
# 현재 상태 저장
temp = pos[:]
# DFS 수행 후 상태 복구
pos[i] = np
dfs(pos, count + 1, sum + M[np])
pos = temp # <- 문제의 지점Gemini:
파이썬에서 리스트는 참조 형태로 전달됩니다. 위 코드에서 일어나는 일은 다음과 같습니다.
temp = pos[:]: 원본 리스트의 얕은 복사본을 만들어 temp에 저장합니다.
pos[i] = np: 부모 함수로부터 넘겨받은 원본 리스트 객체 자체를 수정합니다.
dfs(...): 수정된 원본 리스트가 다음 탐색으로 넘어갑니다.
pos = temp: 여기가 핵심입니다. 이 코드는 변경된 원본 리스트를 복구하는 것이 아닙니다.
단지 현재 스코프의 지역 변수인 pos가 가리키는 메모리 주소를 방금 만든 temp 객체로 바꿔버릴 뿐입니다.
결과적으로, 함수가 끝나고 이전(부모) 호출 단계로 돌아가면,
부모 단계가 알고 있는 원본 pos 객체는 pos[i] = np에 의해 이미 값이 변경된 채로 남아있게 됩니다.
상태 복구(Backtracking)가 실패하는 것입니다.
올바른 해결 방법 3가지
이 문제를 해결하려면 다음 중 하나의 방식을 사용해야 합니다.
방법 1: 변경한 인덱스의 값만 직접 복구 (가장 권장, 속도가 빠름)
리스트 전체를 복사할 필요 없이, 변경된 말의 위치 하나만 저장했다가 되돌려 놓는 백트래킹의 정석적인 방법입니다.
original_pos = pos[i] # 현재 말의 원래 위치 저장
pos[i] = np # 새 위치로 이동
dfs(pos, count + 1, sum + M[np])
pos[i] = original_pos # DFS 종료 후 상태 복구
방법 2: 아예 새로운 복사본을 만들어 다음 단계로 넘기기 (가장 깔끔함)
원본 pos 객체 자체를 훼손하지 않으면 복구 로직이 아예 필요 없어집니다.
temp = pos[:] # 리스트 복사
temp[i] = np # 복사본의 값 수정
dfs(temp, count + 1, sum + M[np]) # 복사본을 넘김
# 원본 pos는 수정되지 않았으므로 복구할 필요 없음2차 수정 버전
import heapq
M = [
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, #20개 #38(19th) -> 40(32th)
# 이동 시작할 때, 10(5th) -> 13(20th), 20(10th) -> 22(23th), 30(15th) -> 28(25th)
13, 16, 19, # 19(22th) -> 25(28th)
22, 24, # 24(24th) -> 25(28th)
28, 27, 26, # 26(27th) -> 25(28th)
25, 30, 35, # 35(30th) -> 40(31th)
40, 0,
]
def isFinished(pos):
return pos == len(M) - 1
def go(pos, is_blue):
if(isFinished(pos)):
return pos
if(is_blue):
if(pos == 5):
return 20
elif(pos == 10):
return 23
else:
return 25
elif(pos == 19 or pos == 30):
return 31
elif(pos == 22 or pos == 24):
return 28
else:
return pos + 1
def isBlue(pos):
return pos == 5 or pos == 10 or pos == 15
def goN(pos, n):
if(isFinished(pos)):
return pos
i = 0
while(i < n):
is_blue = isBlue(pos) if i == 0 else False
pos = go(pos, is_blue)
i += 1
return pos
nums = []
sums = [] # 최대 힙
def dfs(pos, count, sum):
# print(pos, count, "sum:",sum)
if(count == 10):
heapq.heappush(sums, -sum)
return
for i in range(4):
# 이전 말이 출발 안했으면 패스 (최적화)
if(i > 1 and pos[i - 1] == 0):
continue
# 출발 가능한 말인지 확인
if(isFinished(pos[i])):
continue
# 도착 가능한 지점인지 확인
np = goN(pos[i], nums[count])
if(not isFinished(np) and np in pos):
continue
# 현재 상태 저장
temp = pos[i]
# DFS 수행 후 상태 복구
pos[i] = np
dfs(pos, count + 1, sum + M[np])
pos[i] = temp
nums = list(map(int, input().split()))
dfs([0,0,0,0], 0, 0)
print(-sums[0])+)
# 이전 말이 출발 안했으면 패스 (최적화)
if(i > 1 and pos[i - 1] == 0):
continue이 줄의 최적화 효과:
수행 시간 902ms
메모리 사용량 28MB
->
수행 시간 431ms (-52% )
메모리 사용량 25MB (-11%)
나만의 세계 만들어나가기