글 읽기 - 3번 테스트케이스 오류

baj2121 4년 전 0

다른 테스트케이스는 전부 맞는데 , 3번 테스트 케이스에 대해서만 218이 결과로 출력됩니다.

로직을 따라가면서 계속 확인했는데 어디가 문제인지 전혀 찾을 수 가 없어서 부탁드립니다.

#include<iostream>

using namespace std;

int map[4][22] = { 
	{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,0},
{10,13,16,19,25,30,35,40,0},
{20,22,24,25,30,35,40,0},
{30,28,27,26,25,30,35,40,0} 
};
bool visit[4][22];

int maplen[4] = { 21,8,7,8 };

struct Node{
	
	int road;
	int loc;
	bool arrived;
	
};


Node horse[4];
int dice[10];
int maxa = -1;
int result;


bool check(int road,int loc)
{
	for(int i = 0; i < 4; i++)
	{
		if(!horse[i].arrived )
		{
			if(road == horse[i].road && loc == horse[i].loc)
			{
				return false;
			}
		}
	}
	return true;
	
}


void DFS(int cur)
{
	if(cur == 10)
	{
		if(result > maxa)
		{
			maxa = result;
		}
		
		return;
	}
	
	
	
	for(int i = 0; i < 4; i++)
	{
		int newloc = horse[i].loc + dice[cur];
		int temploc = horse[i].loc;
		int temproad = horse[i].road;
		
		if( !horse[i].arrived)
		{
			if(horse[i].road == 0)
			{
				if(newloc == 5)
				{
					if(check(1,0))
					{
						horse[i].loc = 0;
						horse[i].road = 1;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
						horse[i].road = temproad;
					}
					
					
				}
				else if(newloc == 10)
				{
					
					if(check(2,0))
					{
						horse[i].loc = 0;
						horse[i].road = 2;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
						horse[i].road = temproad;
					}
				
				}
				else if(newloc == 15)
				{
					if(check(3,0))
					{
						horse[i].loc = 0;
						horse[i].road = 3;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
						horse[i].road = temproad;
					}
					
				}
				else if(newloc >= maplen[0])
				{
					horse[i].loc = maplen[0];
					horse[i].arrived = true;
					DFS(cur+1);
					horse[i].arrived = false;
					horse[i].loc = temploc;
				}
				else
				{
					if(check(0,newloc))
					{
						horse[i].loc = newloc;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
						
					}
				
				}
			
			}
			else if(horse[i].road == 1)
			{
				if(newloc >= maplen[1])
				{
					horse[i].loc = maplen[1];
					horse[i].arrived = true;
					DFS(cur+1);
					horse[i].arrived = false;
					horse[i].loc = temploc;
				}
				else
				{
					if(check(1,newloc))
					{
						horse[i].loc = newloc;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
						
					}
				
				}
			
			}
			else if(horse[i].road == 2)
			{
				if(newloc >= maplen[2])
				{
					horse[i].loc = maplen[2];
					horse[i].arrived = true;
					DFS(cur+1);
					horse[i].arrived = false;
					horse[i].loc = temploc;
				}
				else
				{
					if(check(2,newloc))
					{
						horse[i].loc = newloc;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
					}
					
				}
			}
			else if(horse[i].road == 3)
			{
				if(newloc >= maplen[3])
				{
					horse[i].loc = maplen[3];
					horse[i].arrived = true;
					DFS(cur+1);
					horse[i].arrived = false;
					horse[i].loc = temploc;
				}
				else
				{
					if(check(3,newloc))
					{
						horse[i].loc = newloc;
						result += map[horse[i].road][horse[i].loc];
						DFS(cur+1);
						result -= map[horse[i].road][horse[i].loc];
						horse[i].loc = temploc;
					}
				
				}
			
			}
			
		}
		
	}
}


int main(void)
{
	
	for(int i = 0; i < 5; i++)
	{
		horse[i] = {0,0,0};
	}
	
	
	for(int i = 0; i <10; i++)
	{
		cin >> dice[i];
	}
	
	DFS(0);
	
	cout << maxa << endl;
	
	
	
	
}

baj2121 4년 전 6

해결 했습니다.

같은 경로가 아닌 경우에도 두 말이 겹치는 case가 존재 하는데 그것에 대한 처리를 해주면 되었습니다.

wksehfdl8 3년 전 0

같은 문제로 고생중입니다.. ㅠㅠ

혹시 같은 경로가 아닌경우에 두말이 겹치는 케이스가 무엇인지 설명해주실수 있을까요..?

song98987 2년 전 0

@wksehfdl8

늦었지만, 제 경우에는

1->1->2->1->3->3->3->1->3->3 으로 이동할 때

마지막 턴에서 40으로 적힌 칸에 1번 말이 위치함에도 3번 말이 40으로 적힌 칸에 이동해서 겹쳤습니다.

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

문제

문제

출처

ICPC

3번 테스트케이스 오류

baj2121 4년 전 0

baj2121 4년 전 6

wksehfdl8 3년 전 0

song98987 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말