[Baekjoon] 1987번: 알파벳

🥅 문제

https://www.acmicpc.net/problem/1987

 

🔍 설계

어떤 알파벳을 중복해서 방문할 수 없으므로, 알파벳에 대한 방문 여부를 visited에 저장한다.

 

말이 최대 연속해서 몇 칸을 지날 수 있는지 구하기 위해서는 DFS를 이용해야 한다. 지나는 경로 중간에 다른 방향으로 경로를 탐색하기 위해 백트래킹을 이용한다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int r, c, result = 0;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
vector<vector<char>> board(20, vector<char>(20));
vector<bool> visited(26);
string s;

void dfs(int cur_x, int cur_y, int temp_result) {
	result = max(result, temp_result);

	for (int i = 0; i < 4; i++) {
		int new_x = cur_x + dx[i];
		int new_y = cur_y + dy[i];
		if (!(new_x >= 0 && new_x < r && new_y >= 0 && new_y < c)) {
			continue;
		}
		int new_alphabet = board[new_x][new_y];
		if (!visited[new_alphabet - 'A']) {
			visited[new_alphabet - 'A'] = true;
			dfs(new_x, new_y, temp_result + 1);
			visited[new_alphabet - 'A'] = false;
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		cin >> s;
		for (int j = 0; j < c; j++) {
			board[i][j] = s[j];
		}
	}

	visited[board[0][0] - 'A'] = true;
	dfs(0, 0, 1);

	cout << result << "\n";

	return 0;
}