백준 1987: 알파벳

문제 요약

세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다.

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

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

문제 분류

• 그래프 이론
• 그래프 탐색
• DFS
• 백트래킹

문제 풀이

2차원 배열을 (0, 0) 위치로부터 같은 문자가 반복되지 않을때만 탐색해 나가면 되는 백트래킹 문제이다.

중복되는 문자의 처리는 string의 find()를 사용해보았지만 시간초과가 발생해서 alphabet이라는 bool타입 배열로 해결했다.

지나온 정점들을 표시할 visited배열과 탐색 방향을 제시할 dir배열을 선언해주었고, 함수의 시작과 끝에는 각 배열을 설정 및 되돌려주는 작업을 해주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int r, c, MAX = 0;
char ary[20][20];
bool visited[20][20], alphabet[27];
int dir[4][2] = { {1,0}, {0,1},{-1,0},{0,-1} };

void dfs(int i, int j, int cnt) {
	MAX = max(MAX, cnt);
	int ni, nj;
	alphabet[ary[i][j] - 'A'] = true;
	visited[i][j] = true;
	for (int k = 0; k < 4; k++) {
		ni = i + dir[k][0];
		nj = j + dir[k][1];
		if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
			if (!visited[ni][nj] && !alphabet[ary[ni][nj] - 'A'])
				dfs(ni, nj, cnt + 1);
		}
	}
	visited[i][j] = false;
	alphabet[ary[i][j] - 'A'] = false;
}

int main()
{
	cin >> r >> c;
	for (int i = 0; i < r; i++)
		scanf("%s", &ary[i]);
	dfs(0, 0, 1);
	visited[0][0] = true;
	cout << MAX;
	return 0;
}