백트래킹(Back Tracking)

쉽게 말하면 가능성이 없는 곳은 되돌아가고 가능성이 있는 곳은 탐색하는 알고리즘.

미로를 생각하면 쉽다. 미로에서 막다른 길을 만나면 되돌아가서 다른 길을 찾게되니까.

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

접근 방법

같은 알파벳이 적힌 칸을 두 번 지날 수 없다에서 백트래킹이 떠올랐다.
백트래킹에서는 DFS를 이용하는게 더 편하므로 DFS를 재귀적으로 실행해서 구현했다.

알파벳은 visited 벡터에 0~25 인덱스에 담아 방문하면 1, 아니면 0으로 설정했다.
DFS 시작시 방문한 알파벳을 1로 설정하고,
탐색 과정에서 방문했던 노드를 다시 사용할 수 있도록 마지막 부분에 visited를 초기화 했다.

풀이

#include <iostream>
#include <vector>
#include <stack>
#include <tuple>

using namespace std;

int r, c;
vector<vector<char>> vec(20, vector<char>(20));
int dirX[4] = {-1, 0, 1, 0};
int dirY[4] = {0, 1, 0, -1};
vector<int> visited(26, 0);
int ans = -1;

void dfs(int x, int y, int dis)
{
    visited[vec[x][y]-'A'] = 1;
    ans = max(dis, ans);
    for (int i = 0; i < 4; i++) {
        int nx = x + dirX[i];
		int ny = y + dirY[i];
		if (nx >= 0 && nx < r && ny >= 0 && ny < c) {
			if (!visited[vec[nx][ny]-'A'])
				dfs(nx, ny, dis + 1);
		}
	}
    visited[vec[x][y]-'A'] = 0;
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> r >> c;

    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> vec[i][j];
        }
    }
    dfs(0, 0, 1);
    cout << ans;
}