글 읽기 - 파이썬 시간초과 + 답은 맞는데 이상한 문제가 있습니다;;;

jhangww 2년 전 0

백트래킹 알고리즘으로 푼건데 시간초과가 나는데요. 더 이해가 안가는건

아래의 코드를 실행해보면 답은 맞게 나오는데 append시킨 coord_set을 종료후 호출해보면 전혀 엉뚱한 숫자들이 들어가 있습니다.

바로 밑에 print("append {}".format(coord)) 를 통해 확인해보면 분명 맞는 좌표들이 저장되고 있는거 같은데

다 돌고 까보면 이상한 좌표 (그것도 딱 한세트가 모든 정답을 대체하고 있습니다) 가 있는데 왜 그러는 걸까요?

시간초과도 더불어서 해결하고 싶지만 일단은 이 점이 너무 이상하고 이해가 안가는데 도와주세요 ㅠㅠ

N = int(input())
coord_set=[]
coord=dict()
num=0

def Q_cord(line,i_li):
    global num
    if line == N:
        coord_set.append(coord)
        #print("append {}".format(coord))
        
    else:
        for i in i_li:
            if (True not in list(abs(list(coord.keys())[k]-line) == abs(list(coord.values())[k]-i) for k in range(line))) and (len({i}-set(list(coord.values())[k] for k in range(line))))!=0 :
                coord[line] = i

                Q_cord(line+1,i_li)
              

Q_cord(0,list(range(N)))
print(len(coord_set))

qwer15417 2년 전 1

디버깅으로 보시면 아시겠지만 9번 줄에 coord가 그대로 들어가서 coord_set 안에 들어있는 값들은 모두 하나의 coord를 참조하고 있게 됩니다.

해결하시려면 coord.copy() 같은 걸 넣어주시면 됩니다.

9번 줄 수정 : coord_set.append(coord.copy())

jhangww 2년 전 1

와우 너무 감사드립니다!

이렇게 변수들이 자동 동기화 (?) 되는 문제를 주의해야겠네요!

시간 초과는 좀 더 해결해보겠습니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과 + 답은 맞는데 이상한 문제가 있습니다;;;

jhangww 2년 전 0

qwer15417 2년 전 1

jhangww 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말