[백준] C++ 1987(알파벳)

 

#include <iostream>

using namespace std;

char arr[21][21];

void DFS(int i, int j, int count, int C[30]);

int result=0;
int row=0;
int col=0;


int main(void)
{
	cin>>row>>col;
	
	for(int i=0; i<row; i++)
	{
		for(int j=0; j<col; j++)
		{
			cin>>arr[i][j];
		}
	}
	int visited[30]={0};
	visited[(arr[0][0])-65]=1;
	DFS(0,0,0,visited);
	cout<<result+1;
	return 0;
}

void DFS(int i, int j, int count, int C[30])
{
	if(count>result)
	{
		result=count;
	}

	int temp1[30];
	int temp2[30];
	int temp3[30];
	int temp4[30];
	for(int k=0; k<=30; k++)
	{
		temp1[k]=C[k];
		temp2[k]=C[k];
		temp3[k]=C[k];
		temp4[k]=C[k];
	}
	
	if(C[int(arr[i+1][j])-65]==0&&i+1<row)
	{
		temp1[(arr[i+1][j])-65]=1;
		DFS(i+1,j,count+1,temp1);
	}
	if(C[int(arr[i-1][j])-65]==0&&i-1>-1)
	{
		temp2[(arr[i-1][j])-65]=1;
		DFS(i-1,j,count+1,temp2);
	}
	if(C[int(arr[i][j+1])-65]==0&&j+1<col)
	{
		temp3[(arr[i][j+1])-65]=1;
		DFS(i,j+1,count+1,temp3);
	}
	if(C[int(arr[i][j-1])-65]==0&&j-1>-1)
	{
		temp4[(arr[i][j-1])-65]=1;
		DFS(i,j-1,count+1,temp4);
	}
	
}

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다.

즉 새로운 알파벳만 밟으면서 이동할 수 있는 거리의 최댓값을 찾는 문제이다.

 

N-퀸 문제를 해결해 봤으면 이 문제를 푸는 것은 어렵지 않을 것이다.

이 문제에서 주의할 점은 visited를 사용해야 한다는 것이다. 만약 이동한 순서대로 배열에 값을 저장하고 for문을 돌려 겹치는 알파벳이 있는지 확인하게 된다면 시간초과가 발생할 것이다.

이 문제에서 visited는 알파벳을 의미한다. (arr[i+1][j])-65 아스키코드를 이용해서 문제를 해결하면 된다.(예 A-65=0)

밟은 적이 없으면 이동이 가능하고 밟은 적이 있다면 이동이 불가능하다. 

 

이 문제를 해결하면서 알게 된 사실인데 

전역변수는 실행과 동시에 0값으로 초기화가 자동으로 되는데 지역변수는 자동으로 초기화가 되지 않는다. 만약 지역변수에 배열을 선언하게 된다면 명시적으로 초기화를 꼭 해주어야 한다.(지역변수는 보통 사용하기 전에 명시적으로 초기화를 하기 때문에 자동으로 초기화를 하게 되면 불필요한 오버헤드가 발생해서 자동으로 초기화하지 않는다고 한다.)