[ Baekjoon - 10/14 ] - 3980번: 선발 명단

• 문제 링크 : https://www.acmicpc.net/problem/3980

3980번: 선발 명단

 

• 소요 시간 : 50분 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     • 11명의 선수가 11개의 포지션에 배치될때, 모두의 능력을 잘 발휘하여 모든 선수의 총 능력치 합의 최대를 출력하는 문제
   • 이해
     
     • 문제가 간단해서 이해가 어렵진 않았다. 
2. 문제를 익숙한 용어로 재정의와 추상화
   • 이해가 어렵지 않아서 생략했다. 
3. 문제를 어떻게 해결할 것인가

   • 

   • 백트래킹을 사용해야 할것같아서 조건을 따지기 위해 그려보았다.
   • 연결되었고, 갈수있는 노드(선수)로 루트에서부터 그려보았는데,
     각 노드는 능력치가 0이 아니고, 부모에서 방문하지 않은 선수이다.
   • 이를 조건으로 DFS를 진행하면 될것같았다
4. 위 계획을 검증
   • 문제 자체는 조건만 잘 지키면 되는 완탐이라 크게 다루진 않겠다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int T,ans;
            static int[][] map;
            static boolean[] vis;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                T = Integer.parseInt(br.readLine());
                while (T-->0){
                    map=new int[11][11];
                    vis=new boolean[11];
                    ans=Integer.MIN_VALUE;
                    for(int i=0; i<11; i++) {
                        StringTokenizer st = new StringTokenizer(br.readLine());
                        for(int j=0; j<11; j++) {
                            map[i][j]=Integer.parseInt(st.nextToken());
                        }
                    }
                    solve(0, 0);
                    System.out.println(ans);
                }
            }
        
            private static void solve(int playerNo, int total) {
                if(playerNo==11) {
                    ans = Math.max(total, ans);
                    return;
                }
        
                for(int i=0; i<11; i++) {
                    if(map[playerNo][i]==0 || vis[i])
                        continue;
                    vis[i]=true;
                    solve(playerNo+1, total+map[playerNo][i]);
                    vis[i]=false;
                }
        
            }
        }

   2. Python 3

      • import sys
        input = sys.stdin.readline
        
        def DFS(num, total):
            global ans, vis
            if num == 11:
                ans = max(ans, total)
                return
        
            for x in range(11):
                if vis[x] or abilityMap[num][x] == 0:
                    continue
                total += abilityMap[num][x]
                vis[x] = True
                DFS(num+1, total)
                total -= abilityMap[num][x]
                vis[x] = False
        
        test_case = int(input())
        for _ in range(test_case):
            abilityMap = [list(map(int, input().split())) for _ in range(11)]
            vis = [False] * 11
            ans = 0
        
            DFS(0, 0)
            print(ans)

 

• 결과

틀렸던 이유는.. 자바를 그대로 파이썬 코드로 변환한뒤 실행한번 안하고 제출했다가 생긴 오류이다.. 테케만큼 반복해야하는데 왜 안넣었지..ㅋㅋ

 

런타임에러도 실행안해서 생긴 오류인데 함수명을 다르게했다가(solve와 DFS) 생긴 오류..

 

확실히 어려운 문제면 틀리지않으려고 계속 고민하다가 제출하는데.. 쉬운문제일수록 바로 제출해버려서 틀리는것같다. 고쳐야지