SWEA 5189 전자카트 (python)

5189. [파이썬 S/W 문제해결 구현] 2일차 - 전자카트 D3

문제

골프장 관리를 위해 전기 카트로 사무실에서 출발해 각 관리구역을 돌고 다시 사무실로 돌아와야 한다.

사무실에서 출발해 각 구역을 한 번씩만 방문하고 사무실로 돌아올 때의 최소 배터리 사용량을 구하시오.

각 구역을 이동할 때의 배터리 사용량은 표로 제공되며, 1번은 사무실을, 2번부터 N번은 관리구역 번호이다.

두 구역 사이도 갈 때와 올 때의 경사나 통행로가 다를 수 있으므로 배터리 소비량은 다를 수 있다.

N이 3인 경우 가능한 경로는 1-2-3-1, 1-3-2-1이며 각각의 배터리 소비량은 다음과 같이 계산할 수 있다.

e[1][2]+e[2][3]+e[3][1] = 18+55+18 = 91

e[1][3]+e[3][2]+e[2][1] = 34+7+48 = 89

e	1	2	3	도착
1	0	18	34
2	48	0	55
3	18	7	0
출발

이 경우 최소 소비량은 89가 된다.

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 첫 줄에 N이 주어지고, 다음 줄부터 N개씩 N개의 줄에 걸쳐 100이하의 자연수가 주어진다. 3<=N<=10

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이과정

전체적으로 도는 것을 못짜겠는 느낌?

문제를 이해를 잘 못한것 같다.... 다시

import sys
sys.stdin = open("input.txt")

T = int(input())

def battery(x, y, total):
    global result
    for i in range(N):
        if not visited[i]



for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]

    result = []



    print("#{} ".format(tc, ))

다음 개선 단계에서는 다음과 같이 풀었다.

T = int(input())

def battery(x, y, total):
    global result
    if y == N-1:
        if total < result:
            result = total
            return
    for i in range(N):

        if not arr[y][i]:
            continue
        if not visited[i]:
            visited[i] = 1
            battery(i, y+1, total + arr[y][i])

        else:
            return


for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0 for _ in range(N)]
    result = 100 * N
    battery(0, 0, 0)

    print("#{} {}".format(tc, result))

66,40,500 이라는 값이 나와 한참 비슷하지 않았다...

아마 2번째 케이스 부터는 result 가 수정되지 않고 나오는 것 같았다.

import sys
sys.stdin = open("input.txt")

T = int(input())

def battery(x, y, total):
    global result
    if y == N and sum(visited) == N:
        if total < result:
            result = total
            return
    elif y > N-1:
        return
    if total > result:
        return
    for i in range(N):

        if not arr[y][i]:
            continue
        if not visited[i]:
            visited[i] = 1
            battery(i, y+1, total + arr[y][i])
            visited[i] = 0



for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0 for _ in range(N)]
    result = 100 * N
    battery(0, 0, 0)

    print("#{} {}".format(tc, result))

다음에는 이렇게 풀었지만 맞지 않았다...

그 이유로는 문제를 잘못 이해했다...

그냥 한 행에서 가장 작은것 찾는식으로 진행했기 때문이다.

풀이

import sys
sys.stdin = open("input.txt")

T = int(input())

# 기본적인 원리는 다음과같다.
# y=0 즉 문제에서는 1열에서 출발하여서 임의의 x값들을 중복되지 않게 모두 바꾼다음
# 마지막 사무실로 돌아오는것 즉, x = 0 이 되는 조건으로 하였다.
# y값은 다음에는 x값이 되는 이어지는 원리이다.

# 배터리가 소모되는 함수
# 각각의 횟수랑 y의값 total 값을 받는다.
def battery(cnt, y, total):
    global result
    # 종료조건으로 만약 N회차이면 마지막 사무실에 돌아와야 하므로
    if cnt == N:
        # 마지막 사무실에 돌아오는 소모량 더해주고
        total += arr[y][0]
        # 총합이 기존의 결과값보다 작다면 갱신해주고 종료한다.
        if total < result:
            result = total
            return
    # 만약 실행 도중에 total 보다 커진다면 그냥 바로 종료한다.
    if total > result:
        return
    # 마지막 사무실에 돌아오는 것을 남겨두고 돌아보자
    for i in range(1, N):
        # 만약 구역에 도착했다면 ( n,n ) 이라면 0이므로 건너뛰기
        if not arr[y][i]:
            continue
        # 만약 방문한 적이 없다면
        if not visited[i]:
            # 방문체크 해주고
            visited[i] = 1
            # 다음 회차로 넘어가고 x값으로 들어오는 값을 y로 넘겨준다.
            battery(cnt+1, i, total + arr[y][i])
            # 방문해제
            visited[i] = 0



for tc in range(1, T+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [0 for _ in range(N)]
    # 100이 최대라고 해서 최대값 다음과 같이 함
    result = 100 * N
    # 1회차 부터 시작한다.
    battery(1, 0, 0)

    print("#{} {}".format(tc, result))

추가

• 실수했던 점은 다음과같다.
  • 무작정 행에서 값을 하나씩 고르고 중복되는 열이 없도록 하는 느낌이었다.
  • 문제를 제대로 이해하지 못했다.
  • 계속 이어지는 구조를 가져야 하는데 그렇지 못했고 그랬기에 tc 3부터는 다르게 나타났다.