글 읽기 - 윷놀이 문제 어디서 틀렸는지 모르겠어요 ㅠㅠ(반례좀 찾아주세요)

ekfrhkquf12 4년 전 1

그래프는 링크드리스트로 구현했고요, (그래프 구현하는건 116번째 줄까지입니다)

시간은 좀 오래 걸려도 예제에 대한 답은 다 나오는데요,

제출하면 틀렸다고 나와서 혹시 반례를 찾아주시거나 코드에 어떤 문제가 있는지 말씀해주시면 감사하겠습니다. ㅠ.ㅠ

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
using namespace std;

typedef struct node {
	node* link;
	node* link2;
	int value;
	bool occupied;
} node;

int sum = 0;
void dfs(vector<pair<node*, int> > mystack, node* piece[], vector<int> data, bool visited[], node* end, node* start);
void calculate(vector<pair<node*, int> > mystack);
int main() {
	//10개 명령의 execution 순서가 정해짐
	//dfs해서 depth == 10일 때 calculate하는 것
	//for i in 4 해서 4개의 말을 이동

	node* start = (node*)malloc(sizeof(node));
	node* top;
	node* temp;
	start->value = 0;
	start->occupied = false;
	temp = start;

	vector<node*> branch;
	for (int i = 2; i <= 40; i += 2) {
		top = (node*)malloc(sizeof(node));
		top->value = i;
		top->occupied = false;
		temp->link = top;
		temp = top;
		if (i % 10 == 0) branch.push_back(top);
	}

	temp = branch.at(0);
	for (int i = 13; i <= 19; i += 3) {
		top = (node*)malloc(sizeof(node));
		top->value = i;
		top->occupied = false;
		temp->link2 = top;
		if (temp!= branch.at(0)) temp->link = top;
		temp = top;
	}

	node* center = (node*)malloc(sizeof(node));
	center->value = 25;
	center->occupied = false;
	top->link2 = center;
	top->link = center;
	
	temp = branch.at(1);
	top = (node*)malloc(sizeof(node));
	top->value = 22;
	top->occupied = false;
	temp->link2 = top;
	temp = top;

	top = (node*)malloc(sizeof(node));
	top->value = 24;
	top->occupied = false;
	temp->link2 = top;
	temp->link = top;
	temp = top;
	top->link2 = center;
	top->link = center;


	temp = branch.at(2);
	for (int i = 28; i >= 26; i--) {
		top = (node*)malloc(sizeof(node));
		top->value = i;
		top->occupied = false;
		temp->link2 = top;
		if (temp!= branch.at(2)) temp->link = top;
		temp = top;
	}
	top->link2 = center;
	top->link = top;

	temp = center;
	for (int i = 30; i <= 35; i += 5) {
		top = (node*)malloc(sizeof(node));
		top->occupied = false;
		top->value = i;
		temp->link2 = top;
		temp->link = top;
		temp = top;
	}
	top->link2 = branch.at(3);
	top->link = branch.at(3);
	temp = branch.at(3);

	node* end = (node*)malloc(sizeof(node));
	end->occupied = false;
	temp->link = end;
	temp->link2 = end;
	end->link = end;
	end->link2 = end;
	end->value = 0;

	vector<int> data;
	for (int i = 0; i < 10; i++) {
		int temp;
		cin >> temp;
		data.push_back(temp);
	}

	vector<pair<node*, int> > mystack;
	bool visited[10];
	for (int i = 0; i < 10; i++)
		visited[i] = false;

	//네 개 말의 위치 정보를 저장하는 배열
	node* piece[4];
	for (int i = 0; i < 4; i++)
		piece[i] = start;

	dfs(mystack, piece, data, visited, end, start);
	printf("%d", sum);
}

void dfs(vector<pair<node*, int> > mystack, node* piece[], vector<int> data, bool visited[], node* end, node* start){
	if (mystack.size() == 10) {
		calculate(mystack);
	}
	else {
		for (int i = 0; i < 4; i++) { // 네 개의 말 중 어느 말을 움직일 것인지를 선택
			if (mystack.size() == 0)
				if (i != 0)
					continue;
			node* v = piece[i];
			if (v != end) { 
				node* buffer = piece[i];
				int jump = data.at(mystack.size());  //그 다음 원소 지시하기 // 지시한 원소는 "몇칸 이동"의 정보가 있음		
				int j = 0;
				if (v->value % 10 == 0 && v!=start) { 
					while (j != jump) {
						//시작지점이 파란색이면 계속 link2를 타고 이동
						v = v->link2;
						j++;
					}
				}
				else
					while (j != jump) {
						v = v->link;
						j++;
					}

				if (v->occupied == false) {
					piece[i]->occupied = false;
					mystack.push_back(make_pair(v, i)); 
					piece[i] = v;
					if (v != end) v->occupied = true;
					dfs(mystack, piece, data, visited, end, start);
					if (buffer->occupied == false) { //돌아갈 수 있는 자리가 비어 있을 때만 돌아가기 -> 이동한 순서대로 빠지니 없어도 되는 조건
					v->occupied = false;
					piece[i] = buffer;
					if (piece[i] != start) piece[i]->occupied = true; //start일때는 제외
					mystack.pop_back();
					}
				}
			}
		}
	}
}

void calculate(vector<pair<node*, int> > mystack) {
	int i = 0;
	int temp = 0;
	node* next;
	while (i != 10) {
		next = mystack.at(i).first;
		temp += next->value;
		i++;
	}
	if (temp > sum) 
		sum = temp;
}

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

문제

문제

출처

ICPC

윷놀이 문제 어디서 틀렸는지 모르겠어요 ㅠㅠ(반례좀 찾아주세요)

ekfrhkquf12 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말