[백준][BOJ-3980][자바] 선발 명단

www.acmicpc.net/problem/3980

3980번: 선발 명단

import java.io.*;
import java.util.*;

public class Main {
	static int max;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		int[][] map;
		boolean[] visited;
		
		for(int tc =0; tc<T; tc++) {
			map = new int[11][11];
			visited = new boolean[11];
			max= 0;
			
			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());
				}
			}
			
			dfs(0,0,map,visited);
			System.out.println(max);
		}
		
	}

	public static void dfs(int cnt, int sum, int[][] map, boolean[] visited) {
		if(cnt == 11) {
			max = Math.max(max, sum);
			return;
		}
		
		for(int i=0; i<11; i++) {
			if(map[cnt][i] == 0 || visited[i]) continue;
			visited[i] = true;
			dfs(cnt+1, sum+map[cnt][i], map, visited);
			visited[i] = false;
		}
	}
}

정리

• N이 11까지라서 완전 탐색 돌리는데 문제가 없다.
• 문제에서 주어진 조건에 따라 0이거나 이미 포지션이 정해진 경우는 넘어간다.
• visited를 true로 해주고 그중 값을 선택해서 sum에 더해주면서 재귀를 한다.
• 11까지 갔을 때 max값을 구한다.