[백준 3980][💛4] 선발 명단 (DFS, 백트래킹)

🚀 난이도

💛 골드 4

🚀 문제

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

🚀 내 풀이 ⭕

N-Queen 문제와 매우 유사한 기본적인 백트래킹 문제였다! 행을 선수로, 열을 포지션으로 생각하고 열이 중복되지 않도록 선택해나가면 되는 문제였다.

#include <bits/stdc++.h>

using namespace std;

int answer = 0;
int arr[11][11];  // row : 선수    col : 포지션
bool visited[11]; // 11개의 포지션별로 방문 체크 (선수 배정이 되었는지 여부)

void dfs(int player, int sum) {  // 11명의 선수들 각각 순서대로 포지션에 배정 (중복되지 않게!)
	
	if (player == 11) {  // 여기까지 왔다면 11명의 모든 선수를 포지션 중복되지 않게 전부 배정했다는 것.
		answer = max(answer, sum);
		return;
	}

	for (int position = 0; position < 11; ++position) {
		if (arr[player][position] != 0 && !visited[position]) { // 현재 선수player를 현재 position 에 배정하고 다음 선수를 검사하러 가려면 능력치가 있고 현재 경로의 이전에서 배정된적 없는 포지션이어야 한다. 
			visited[position] = true; // 해당 포지션에 선수 배정 체크
			dfs(player + 1, sum + arr[player][position]);  // 다음 선수 배정하러 출발. 
			visited[position] = false; // 더 이상 중복되지 않게 배정할 포지션이 없어서 Back 했거나 성공했거나 뭐든 간에 방문 체크는 해제해주어야 또 다른 미래의 케이스에서 선택될 수 있다.
		}
	}  // for 문의 if 에 걸리는게 없이 종료됐다면 자연스럽게 Back
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int C;
	cin >> C;
	while (C--) {
        // 입력
		for (int i = 0; i < 11; ++i) 
			for (int j = 0; j < 11; ++j) 
				cin >> arr[i][j];
		
        // 백트래킹 기법으로 '포지션 중복되지 않게 선수를 모두 배정'하는게 가능한 모든 경우를 구하여 max 업데이트 
		dfs(0, 0);
		
        cout << answer << '\n';
		answer = 0;
	}
}

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기