[백준/C++] 1987. 알파벳

문제

www.acmicpc.net/problem/1987

1987번: 알파벳

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

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

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

풀이

DFS를 이용하면 된다!

보통 DFS를 이용할 때, 전체 table과 같은 크기의 visited 배열을 만들어서 해당 칸을 방문했는지를 확인하지만, 이번 문제에서는 알파벳 크기의 visited 배열을 만들어서, 해당 알파벳이 쓰여있는 칸을 방문했는지를 검사하면 되는 문제였다. 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int R, C;
char table[21][21];

int dc[4] = { -1,0,1,0 };
int dr[4] = { 0,-1,0,1 };
int maxCount = 1; //시작점은 무조건 지나는 것으로 하기때문에 1로 초기화 
int cnt = 1;

void DFS(bool visited[], int r, int c) {
	char temp  = table[r][c];
	visited[temp - 'A'] = true;

	for (int i = 0;i < 4;i++) {
		int new_c = c + dc[i];
		int new_r = r + dr[i];

		if (-1 < new_c && -1 < new_r && C > new_c && R > new_r) {
			char next = table[new_r][new_c];

			if (!visited[next - 'A']) { //지나간 적이 없는 알파벳이면! 
				maxCount = max(maxCount, ++cnt);
				DFS(visited, new_r, new_c);
				--cnt;
			}
		}
	}
	visited[temp - 'A'] = false;
}
int main(void) {
	cin >> R >> C;
	for (int r = 0;r < R;r++) {
		for (int c = 0;c < C;c++) {
			cin >> table[r][c];
		}
	}

	bool visited[26] = { 0, };
	DFS(visited, 0, 0);
	cout << maxCount << endl;
	return 0;
}

결과