백준 알파벳

해당 문제는 백준온라인 저지에서 나온 문제입니다.

해결 방식

백트래킹 알고리즘을 활용하여 작성하였습니다
백트래킹 자료 1
백트래킹 자료 2
두가지 블로그를 참고하였습니다.

해결 방식을 고른 이유

인접한 모든 노드를 집어넣고 탐색을 시작하는 BFS알고리즘의 방식은 문제의 조건때문에 선택하기가 힘들다고 판단하였습니다. 따라서 DFS방식을 활용한 백트래킹 알고리즘을 선택하였습니다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

char map[20][20];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };//이동할 방향

vector<char> road;
int cnt =  0;
int R, C;//R이 세로 C가 가로
bool	isValid(char num)//중복되지 않는 문자인지 검사
{
	if (road.empty())
		return true;
	for (int i = 0; i < road.size(); i++)
	{
		if (road[i] == num)
			return false;
	}
	return true;
}

void solution(int x, int y)
{
	road.push_back(map[y][x]);
	for (int i = 0; i < 4; i++)
	{
		if (x + dir[i][0] >= C || y + dir[i][1] >= R)
			continue;
		if (x + dir[i][0] < 0 || y + dir[i][1] < 0)
			continue;
		if (!isValid(map[y + dir[i][1]][x + dir[i][0]]))
			continue;
		solution(x + dir[i][0], y + dir[i][1]);
	}
	if (!road.empty())//[1]
	{
		if ((int)road.size() > cnt)
			cnt = (int)road.size();
		road.pop_back();
	}
}

int main()
{
	string str;
	cin >> R >> C;
	for (int i = 0; i < R; i++)
	{
		cin >> str;
		for (int j = 0; j < C; j++)
		{
			map[i][j] = str[j];
		}
	}
	solution(0, 0);
	cout << cnt << endl;
}

코드 해설

코드의 핵심 부분은 solution 함수입니다. 반복문을 돌며 상하좌우 조건에 맞는 경로를 재귀로 호출하여 이동합니다. 탐색이 끝난 경로는 리스트에서 제외해야 하기 때문에 [1]의 제어문을 두어 현재 경로와 최장 경로를 비교하고(현재 경로가 크다면 cnt를 이로 바꿔줍니다.) pop_back을 통해 마지막으로 이동한 경로를 지워 다음 탐색을 진행합니다.