글 읽기 - 백트래킹 알고리즘

ghwjdgks 3년 전 0

일곱난쟁이를 풀다가 제가 푼 방식이 백트래킹으로 푼것이 맞는지 궁금해서 질문드립니다.

백트래킹이란, 구조적으로는 DFS와 비슷하나 가치지기(조건에 맞지 않으면 break 또는 return)를 적용한다는 점에서 차이가 있다고 알고 있는데 제가 푼 방식이 백트래킹으로 접근한것이 맞는지 궁금하여서 질문드립니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> dwaf;//난쟁이 키 값 배열
vector<int> real_dwaf;//진짜 난쟁이 키 값 배열
bool check[100]; //탐색 난쟁이 check

void backtracking(int sum, int count) {

	if (count == 7 && sum == 100) {
		sort(real_dwaf.begin(), real_dwaf.end());
		
		for (int i = 0; i < real_dwaf.size(); i++) {
			cout << real_dwaf[i] << "\n";
		}

		exit(0);//system call 탈출
	}

	if (count > 7 || sum>100) {
		return;

	}
	
	for (int i = 0; i < dwaf.size(); i++) {

		if (check[dwaf[i]] == false) {

			check[dwaf[i]] = true;
			real_dwaf.push_back(dwaf[i]);

			backtracking(sum + dwaf[i], count + 1);

			check[dwaf[i]] = false;
			real_dwaf.pop_back();
		}

	}

	return;

}



int main(void) {

	
	int n = 9;

	while (n--) {
		int input;
		cin >> input;
		dwaf.push_back(input);
	}
	backtracking(0, 0);

}

djm03178 3년 전 1

맞게 잘 구현하셨습니다.

ghwjdgks 3년 전 0

정말 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

백트래킹 알고리즘

ghwjdgks 3년 전 0

djm03178 3년 전 1

ghwjdgks 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말