[swea] 5209. 최소 생산 비용 / python 파이썬

문제

 

thinking

아주 전형적인 백트래킹 & dfs 문제이다 !

모든 경우를 전부 따져보되, 이미 답이 안되는 경우(값이 기존 결과값보다 큰 경우)는 바로 중단하면 된다.

열과 행이 겹치면 안되므로 dfs라는 함수의 인자로 행(i)을 넣어, 행을 증가시키며 경우를 체킹했고,

visited 라는 리스트를 만들어 열의 방문여부를 확인하도록 코드를 구성했다.

 

코드

def dfs(i, tmp):  # 행, 현재 타임 합
    global res
    if tmp >= res:
        return
    if i == N:
        res = min(tmp, res)
        return

    for j in range(N):
        if not visited[j]:
            visited[j] = 1
            dfs(i+1, tmp+a[i][j])
            visited[j] = 0


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    res = 987654321
    visited = [0]*N  # 열 체크
    dfs(0, 0)
    print("#{} {}".format(tc, res))