[골드4] 3980번 : 선발 명단

Quesuemon·2021년 4월 7일
0

코딩테스트 준비

목록 보기
66/111

🛠 문제

https://www.acmicpc.net/problem/3980


👩🏻‍💻 해결 방법

dfs를 통해 문제를 해결할 수 있었다
dfs의 인자로 인덱스와 현재 sum 값을 설정하고 처음에는 dfs(0,0)으로 함수를 호출했다
함수 안에서는 graph를 하나씩 방문해주며, 방문하지 않았을 경우 방문처리를 해주고 인덱스+1과 현재 sum에 graph 값을 더한 것을 시작점으로 dfs를 재귀적으로 호출하였다
idx가 11이 됐을 경우, result를 최댓값으로 갱신해주었다


소스 코드

import sys
input = sys.stdin.readline

def dfs(idx, now):
  global result 

  if idx == 11:
    result = max(result, now)
    return
  
  for j in range(11):
    if visit[j]: continue
    if graph[idx][j]:
      visit[j] = 1
      dfs(idx+1, now + graph[idx][j])
      visit[j] = 0

T = int(input())
for _ in range(T):
  graph = [list(map(int, input().split())) for _ in range(11)]
  result = 0
  visit = [0] * 11

  dfs(0, 0)

  print(result)

0개의 댓글