[BOJ] 1987 알파벳(DFS, 백트래킹)

www.acmicpc.net/problem/1987

1987번: 알파벳

범주: DFS, 백트래킹

시간복잡도: ??

설명:

백트래킹을 진행하며 노드를 판단한다.

1) 다음 노드(4방향)는 현재 한번도 만나지 않은 알파벳이다 -> 재귀

2) 다음 노드(4방향) 중 어떠한 곳도 이동할 수 없다 -> 경로 길이를 얻은 후, 최대인지 평가

 

시도:

1) alpha 배열을 parameter로 보냈었다. -> 성공했지만 시간이 오래 걸림. 또한 배열의 크기가 컸을 경우(ex. 스도쿠, N-     Queen 등)에는 parameter로 사용할 수 없으므로, global 변수로 변경해야 한다. 

2) global 변수로 바꾸어도 다른 경로에 영향을 주지 않으므로, 성공적으로 구현했고, 시간도 적게 걸림.

 

가져갈 수 있는 팁:

1) 백트래킹을 이용한 경우의 수 혹은 경로 탐색의 경우, global 변수로 상태 배열(ex. alpha 배열)을 이용해도 경로의 독     립성은 지켜진다.  그러니 안심하고 써도 된다.

 

#include<bits/stdc++.h>

using namespace std;

int R, C;
int pos[21][21];
int big;
int orient[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int alpha[26];

void dfs(int r, int c, int dist)
{
	int check = 0;
	
	for(int i = 0; i < 4; i++)
	{
		int nr = r + orient[i][0];
		int nc = c + orient[i][1];
		
		if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
		
		int tmp = pos[nr][nc];
		
		if(alpha[tmp] == 1) continue; 
		
		check = 1;
		
		alpha[tmp] = 1;
		dfs(nr, nc, dist+1);
		alpha[tmp] = 0;
	}
	
	if(check == 0)
	{
		big = max(big, dist);	
	}	
	
	return;
}

int main()
{
	//scanf를 쓸 거면 지운다  
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	

	cin >> R >> C;
	
	for(int i = 0; i < R; i++)
	{
		string str;
		cin >> str;
		
		for(int j = 0; j < C; j++)
		{
			pos[i][j] = str[j] - 'A';	
		}
	}
	
	memset(alpha, 0, sizeof(alpha));
	alpha[pos[0][0]] = 1;
	
	big = 1;
	
	dfs(0, 0, 1);
	
	cout << big;
	
	return 0;
}

 

주의할 점:

입력으로 주어진 문자들이 붙어 있는 형태였기에 받아주는 방법이 2가지로 나뉘었다.

1) scanf("%c",__)

2) cin >> string 후에 직접 대입

scanf를 썼을 때, 줄바꿈도 함께 들어가게 될 가능성이 높다. string을 쓰는 것이 더 안정적이다.