글 읽기 - 백트래킹 시간초과가 이해되지 않습니다.

2015136077 3년 전 0

최대값을 구하는 문제이기 때문에 적어도 4방향이 모두 갈 수 있는지 확인한 후, 갈 수 없으면 max값을 비교하는 방식으로 구현했습니다. 재귀적으로 들어가는 방식이구요. 어느 부분에서 시간초과가 발생할 여지가 있는지 솔직히 모르겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::string> alphabet;
std::string alphabet_kind;
std::string pass_alphabet;
int stack = 0;
int max = 0;
int R, C;

//c값을 가지는 노드를 지나도 되는지 물어보는 코드
bool is_ok_passed(char c) {
	for (int i = 0; i < pass_alphabet.size(); i++) {
		if (pass_alphabet[i] == c) return false;
	}
	return true;
}

//알파벳 종류 알려주는 코드
void alphabet_num() {
	for (int i = 0; i < alphabet.size(); i++) {
		alphabet_kind += alphabet[i];
	}
	sort(alphabet_kind.begin(), alphabet_kind.end());
	alphabet_kind.erase(std::unique(alphabet_kind.begin(), alphabet_kind.end()), alphabet_kind.end());

}

//오른쪽으로 가는게 괜찮은지 알려주는 코드
bool right_is_OK(int row, int col) {
	
	if (col + 1 < C) {
		if (is_ok_passed(alphabet[row][col + 1])) return true;
	}
	return false;
}

//왼쪽으로 가는게 괜찮은지 알려주는 코드
bool left_is_OK(int row, int col) {
	if (col - 1 >= 0) {
		if (is_ok_passed(alphabet[row][col - 1])) return true;
	}
	return false;
}

//아래쪽으로 가는게 괜찮은지 알려주는 코드
bool bottom_is_OK(int row, int col) {
	if (row + 1 < R) {
		if(is_ok_passed(alphabet[row + 1][col])) return true;
	}
	return false;
}

//위쪽으로 가는게 괜찮은지 알려주는 코드
bool top_is_OK(int row, int col) {
	if (row - 1 >= 0) {
		if(is_ok_passed(alphabet[row - 1][col])) return true;
	}
	return false;
}



void calculate(int row, int col) {
	
	if (row == 0 && col == 0) {
		pass_alphabet.push_back(alphabet[row][col]);
		stack++;
	}

    //오른쪽 아래 왼쪽 위 순으로 방향을 체크함
    //체크해서 4방향이 모두 안되는걸 확인하면 그 경로가 최대이므로 이전 값과 max 비교
	if (right_is_OK(row, col)) {
		pass_alphabet.push_back(alphabet[row][col + 1]);
		stack++;
		calculate(row, col + 1);
		pass_alphabet.pop_back();
		stack--;
	}
	if (bottom_is_OK(row, col)) {
		pass_alphabet.push_back(alphabet[row + 1][col]);
		stack++;
		calculate(row + 1, col);
		pass_alphabet.pop_back();
		stack--;
	}
	if (left_is_OK(row, col)) {
		pass_alphabet.push_back(alphabet[row][col-1]);
		stack++;
		calculate(row, col - 1);
		pass_alphabet.pop_back();
		stack--;
	}
	if (top_is_OK(row, col)) {
		pass_alphabet.push_back(alphabet[row - 1][col]);
		stack++;
		calculate(row - 1, col);
		pass_alphabet.pop_back();
		stack--;
	}
	max = std::max(max, stack);


}



int main() {
	
	scanf("%d %d", &R, &C);
	std::string tmp;
	for (int i = 0; i < R; i++) {
		std::cin >> tmp;
		alphabet.push_back(tmp);
	}
	alphabet_num();
	calculate(0,0);
	printf("%d", max);
}

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

문제

문제

출처

ICPC

백트래킹 시간초과가 이해되지 않습니다.

2015136077 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말