글 읽기 - 어디서 틀렸는지 알고싶습니다. vscode에서는 35가 나옵니다..

piousangel 2년 전 0

어디서 틀렸는지 알려주실분 계십니까... 부탁드리겠습니다..ㅠㅠ

n = int(input())

board = [ list(map(int, input().split())) for i in range(n)]
# visited = [[False] * n for i in range(n)]
minCost = 100000001

def dfs(board, visited, cnt, cost, Idx, startIdx):
    global minCost
    if cnt == len(board)-1:
        # print(visited)
        if board[Idx][startIdx] != 0:
            cost += board[Idx][startIdx]
            minCost = min(minCost, cost)
     
        return
    
    for i in range(n):
        if visited[i] != True and board[Idx][i] != 0:
            visited[i] = True
            cost += board[Idx][i]
            dfs(board, visited, cnt+1, cost, i, startIdx)
            visited[i] = False
    
for i in range(n):     #시작점 0,1,2,3
    cost = 0
    visited = [False] * n
    visited[i] = True
    dfs(board, visited, 0, cost, i, i)

print(minCost)

kgw1704 2년 전 0

중간에 cost값을 더해주는 과정에서 저렇게 하시면 cost값이 함수를 돌릴동안 계속 누적됩니다.

cost를 더하는 과정을 밑에 코드처럼 바꾸시면 됩니다.

n = int(input())

board = [ list(map(int, input().split())) for i in range(n)]
# visited = [[False] * n for i in range(n)]
minCost = 100000001

def dfs(board, visited, cnt, cost, Idx, startIdx):
    global minCost
    if cnt == len(board)-1:
        # print(visited)
        if board[Idx][startIdx] != 0:
            cost += board[Idx][startIdx]
            minCost = min(minCost, cost)
     
        return
    
    for i in range(n):
        if visited[i] != True and board[Idx][i] != 0:
            visited[i] = True
            dfs(board, visited, cnt+1, cost + board[Idx][i], i, startIdx)
            visited[i] = False
    
for i in range(n):     #시작점 0,1,2,3
    cost = 0
    visited = [False] * n
    visited[i] = True
    dfs(board, visited, 0, cost, i, i)

print(minCost)

kgw1704 2년 전 0

그리고 어차피 시작점을 포함안한다고 생각하면 모든 점을 한번씩만 방문하는 것이기 때문에 시작점을 for문으로 돌릴필요 없이 그냥 0에서만 시작해도 모든 값을 구할 수 있습니다.

저도 잘하지는 못하지만 나름 최적화해봤습니다. 참고하시면 좋을것같아요!

import sys

n = int(sys.stdin.readline())

board = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
visited = [False for _ in range(n)]
minCost = 100000001

def dfs(visited, cnt, cost, Idx):
    global minCost
    if cnt == n-1:
        if board[Idx][0] != 0:
            minCost = min(minCost, cost + board[Idx][0])
        return
    
    for i in range(1,n):
        if visited[i] == False and board[Idx][i] != 0:
            visited[i] = True
            dfs(visited, cnt+1, cost + board[Idx][i], i)
            visited[i] = False

dfs(visited, 0, 0, 0)
print(minCost)

piousangel 2년 전 1

정말 감사합니다 선생님...! 자세한 답변 너무너무 감사드립니다. 언제나 좋은 일만 가득하시길 바라겠습니다.

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

문제

문제

출처

ICPC

어디서 틀렸는지 알고싶습니다. vscode에서는 35가 나옵니다..

piousangel 2년 전 0

kgw1704 2년 전 0

kgw1704 2년 전 0

piousangel 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말