2105. [모의 SW 역량테스트] 디저트 카페

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

정말 힘들게 풀었다....

1. 방향에 대한 설정 

-> 자꾸 시간초과가 났는데 그 이유중 가장 큰 것은 회전 방향을 오른쪽과 왼쪽 두개를 다 고려했기 때문 

결과적으로 오른쪽으로 회전하나 왼쪽으로 회전하나 거치는 사각형은 모두 같기 때문에 하나만 설정해야함.

2. 이전 방향에 대한 다음 방향 결정

-> 사각형을 만들기 위해서 이전에 들어오는 방향을 살펴 볼 필요가 있다.

예를들어 오른쪽 아래로 내려오는 경우에 이것이 다시 왼쪽 아래로 이동한다면 사각형이 아닌 모양으로 출발점에 들어온다던가, 필요없는 재귀가 반복되어 시간이 증가함.

 

가장 크게는 이 두가지를 고려해야 하고 , 처음 장소에 어떻게 들어올 것인지에 대한 고민을 하면된다.

나는 단순히 좌표를 전역 데이터에 집어넣고 왼쪽 회전이므로 현재 좌표로 부터 x축 -1 y축 -1 이동시 전역 좌표와 같은가를 비교해서 최초 좌표를 확인했다.

 

 

#include<iostream>


using namespace std;
bool dis[101];

int arr[21][21];




int startx , starty;

int maxa;
int N;

void DFS(int i,int j ,int count,int dir)
{
	
		if(i == starty && j == startx)
		{
			
			if(count > maxa)
			{
			
				
			
				maxa = count;
				
			}
	
			
		}
		else
		{
		
		
		
		
	
			
			
			
			if( i-1 == starty && j-1 == startx)
			{
			
				DFS(i-1,j-1,count+1,2);
				
			}
			else
			{
				
				if(i+1 < N && j+1 < N && dir != 3)
					
					if(!dis[arr[i+1][j+1]])
					{
						
						dis[arr[i+1][j+1]] = true;
						
						
					
						
						DFS(i+1,j+1,count+1,1);
						
					
						dis[arr[i+1][j+1]] = false;
					
						
					}
				}
				
				
				if(i-1 >= 0 && j-1 > 0  && starty < i-1 && dir != 0)
				{
					
					if( !dis[arr[i-1][j-1]])
					{
						
						dis[arr[i-1][j-1]] = true;
						
						
				
						
						DFS(i-1,j-1,count+1,2);
						
						
						dis[arr[i-1][j-1]] = false;
					
						
					}
				}
				
				
				if(i+1 < N && j-1 >= 0 && dir != 1 )
				{
					
					if( !dis[arr[i+1][j-1]])
					{
						
						dis[arr[i+1][j-1]] = true;
						
						
					
						DFS(i+1,j-1,count+1,0);
						
					
						dis[arr[i+1][j-1]] = false;
						
						
					}
				}
				
				
				if(i-1 > 0 && j+1 < N && starty < i-1 && dir != 2 )
				{
					
					if( !dis[arr[i-1][j+1]])
					{
						
						dis[arr[i-1][j+1]] = true;
					
						
					
						DFS(i-1,j+1,count+1,3);
						
						
						dis[arr[i-1][j+1]] = false;
						
					}
				}
				
				
				
			
			
			
			
			
			
		}
	
			
			
			
			
			
		}
	
	
	
	
	
	
	
	
		
		
		
		
		
    
	
	
	



int main(void)
{
	
	
	int tc;
	cin >> tc;
	
	
	for(int t = 1; t <= tc; t++)
	{
		
		
		cin >> N;
		
		
		for(int i = 0; i < N; i++)
		{
			
			for(int j = 0; j < N; j++)
			{
				
				cin >> arr[i][j];
				
				
			}
		}
		
		
		
		for(int i = 1; i <=100; i++)
		{
			dis[i] = false;
		}
		
		
		maxa = 0;
		
		for(int i = 0; i < N; i++)
		{
			
			for(int j = 0; j < N; j++)
			{
				
				if( !(j>0 && j<N-1))
				{
					
					continue;
				}
				else{
					
					
					
					
					dis[arr[i][j]] = true;
					starty = i;
					startx = j;
					
					
					
					
							
						if(!dis[arr[i+1][j-1]])
						{
							
								
								
								dis[arr[i+1][j-1]] = true;
								
						     	DFS(i+1,j-1,1,0);
							
								dis[arr[i+1][j-1]] = false;
							
								
						}
					
					
					
			
					
					
					
						
					
					
					
					dis[arr[i][j]] = false;
				}
				
				
				
				
				
				
				
			}
		}
		
		if(maxa)
		{
		cout << "#"<<t<<" "<<maxa<<endl;
	    }
	    else{
	    	
	    	cout<<"#"<<t<<" "<<-1<<endl;
		}
		
		
		
		
	}
	
	
	
	
}