[SWEA 코딩] S/W 문제해결 응용 금속막대 - PYTHON #1259

소스 코드

def dfs(idx):
    global temp
    global max_lst

    for e in range(n):

        # 방문한적 없고, 암나사 == 수나사이면
        if check_lst[e] == 0 and sort_lst[e][0] == idx:

            # 방문 체크
            check_lst[e] = 1

            # temp에 암 수 나사 추가
            temp.append(sort_lst[e][0])
            temp.append(sort_lst[e][1])

            # 함수 실행
            dfs(sort_lst[e][1])

    # max_lst보다 temp의 길이가 길면(현재의 최대 길이면)
    if len(max_lst) < len(temp):
        max_lst = temp

    return

T = int(input())

for tc in range(1,1+T):
    n = int(input())

    temp_lst = list(map(str,input().split()))

    # append 안 하기 위해(속도 높이기 위해)
    lst = [0 for _ in range(n)]

    # lst에 저장
    for q in range(n):
        lst[q] = [temp_lst[2*q], temp_lst[2*q+1]]

    # 정렬
    sort_lst = sorted(lst, key=lambda x:x[0])

    # 최대 길이 저장
    max_lst = []

    for w in range(n):

        # 방문 확인용
        check_lst = [0 for _ in range(n)]
        temp = [sort_lst[w][0],sort_lst[w][1]]
        check_lst[w] = 1
        dfs(sort_lst[w][1])
        check_lst[w] = 0

    print('#{}'.format(tc),end=' ')
    for r in max_lst:
        print(r, end=' ')
    print()

 

---

해결 방법

1. 조건을 n을 20 이하, 암나사의 크기의 중복은 없고, 수나사의 크기의 중복은 없다로 제한(주어진 조건이 부족하기 때문)

 

2. return 하면서 돌아갈 필요 없음(암나사와 수나사의 크기가 1개만 존재하기 때문 == 하나만 찾으면 같은 숫자는 더 확인할 필요 없음)

 

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.