[SWEA 코딩] S/W 문제해결 응용 최적 경로 - PYTHON #1247

소스 코드

def search(idx, score):
    global res

    # 가지치기
    if res < score:
        return

    # 모든 곳 다 방문했으면
    if check.count(1) == n:

        # 마지막 방문지에서 집까지 거리 더해주기
        score += abs(customer[idx*2] - home[0]) + abs(customer[idx*2+1] - home[1])

        if res > score:
            res = score

        return

    for r in range(n):
        if check[r] == 0:
            check[r] = 1
            search(r, score + cu_cu[idx][r])
            check[r] = 0

    return

T = int(input())

for tc in range(1,1+T):

    # 고객 수
    n = int(input())

    # 회사 , 집 , 고객
    arr = list(map(int,input().split()))

    # 회사 좌표
    company = arr[:2]

    # 집 좌표
    home = arr[2:4]

    # 고객 좌표
    customer = arr[4:]

    # 거리 확인하기
    # 회사 -> 고객
    co_cu = [0 for _ in range(n)]

    for first in range(n):
        co_cu[first] = abs(company[0] - customer[first*2]) + abs(company[1] - customer[first*2+1])

    # 고객 -> 고객
    cu_cu = [[0]*n for _ in range(n)]

    for q in range(n):
        for w in range(n):
            cu_cu[q][w] = abs(customer[q*2] - customer[w*2]) + abs(customer[q*2+1] - customer[w*2+1])

    # 방문 체크
    check = [0 for _ in range(n)]

    # 최소 값
    res = 99999999999

    # 첫 번째 집 선택
    for e in range(n):

        # 방문
        check[e] = 1

        # 시작 위치, 현재까지의 거리
        search(e, co_cu[e])

        # 방문 해제
        check[e] = 0

    print('#{} {}'.format(tc,res))

 

---

해결 방법

1. 제한 시간은 30초이고, tc는 10개, N(고객)의 최대 값은 10 이므로 경우의 수는 10!이라고 가정 했음(아닐 수 있음)

 

2. 문제에서 효율성을 배제하고 계산하라고 강조했기 때문에 모든 경우의 수를 확인

 

3. dfs를 통해 모든 경우를 확인

---

느낀 점

분명 쉬운 문제이고, 비슷한 문제를 많이 풀었던 것 같은데...

 

오랜만에 풀려니깐 잘 안풀림... 원래는 효율적인 방법으로 문제를 해결하려 했지만

 

도저히 머리가 안굴러가서... 그냥 다 돌림 ㅠㅠ

 

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

 

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

 

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