[SWEA] Q3752 가능한 시험 점수

[SWEA] Q3752 가능한 시험 점수

Question

Language: Python

Difficulty: D5

해당 문제에서는 효율성을 따지지 않기 때문에 모든 노드에 대한 방문을 수행해서 가장 짧은 거리를 구할 수 있다.

Solution 1

from math import inf

def dfs(count,visited,distance,current_location,house_coordinate):
    global min_distance
    if count==n:
        min_distance=min(min_distance,distance+abs(house_coordinate[0]-current_location[0])+abs(house_coordinate[1]-current_location[1]))
        return

    for i in range(n):
        if i not in visited:
            dfs(count+1,visited+[i],distance+abs(current_location[0]-coordinates[i][0])+abs(current_location[1]-coordinates[i][1]),coordinates[i],house_coordinate)

def solution():
    global coordinates,min_distance
    coordinates=[]
    min_distance=inf

    company_coordinate=locations[0],locations[1]
    house_coordinate = locations[2], locations[3]

    for i in range(2,n+2):
        coordinates.append((locations[i*2],locations[i*2+1]))

    dfs(0,[],0,company_coordinate,house_coordinate)

if __name__ == "__main__":
    n=0
    locations=[]
    coordinates=[]
    min_distance=inf
    with open("input.txt","r" ) as file:
        test_cases=int(file.readline())
        for case in range(test_cases):
            n=int(file.readline())
            locations=list(map(int,file.readline().split()))
            solution()
            print(f"#{case+1} {min_distance}")

하지만, 본래 이 문제의 유형은 2098 문제와 같은 TSP 문제이다.

Solution 2

from math import inf

def manhattan_distance(src,des):
    return abs(src[0]-des[0])+abs(src[1]-des[1])

def tsp(visited,index):
    #모든 노드를 다 거친 경우:
    if visited==(1<<n) -1:
        return manhattan_distance(coordinates[index],coordinates[-1])

    #처음 방문하는 경우가 아닌 경우
    if dp[index][visited] != inf:
        return dp[index][visited]

    #0번 노드는 회사로 다시는 접근할 일이 없다.
    for next_index in range(1,n+1):
        #방문하지 않은 경우에 대해서
        if 1 << (next_index-1) & visited ==0:
            dp[index][visited]=min(dp[index][visited],tsp(visited|1<<(next_index-1),next_index)+manhattan_distance(coordinates[index],coordinates[next_index]))

    return dp[index][visited]

def solution():
    global coordinates,dp
    coordinates=[]
    dp=[[inf] * (1<<n) for _ in range(n+1)]

    #회사의 위치
    coordinates.append((locations[0],locations[1]))

    #각각의 집에 대한 위치
    for i in range(2, n + 2):
        coordinates.append((locations[i * 2], locations[i * 2 + 1]))
    
    #집의 위치
    coordinates.append((locations[2], locations[3]))

    return tsp(0,0)

if __name__ == "__main__":
    n=0
    locations=[]
    coordinates=[]
    dp=[]
    with open("input.txt","r" ) as file:
        test_cases=int(file.readline())
        for case in range(test_cases):
            n=int(file.readline())
            locations=list(map(int,file.readline().split()))
            print(f"#{case+1} {solution()}")