백준 1987번 알파벳 ( C++ )

문제

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

 

해설

여러개의 루트 중에 가장 긴 루트를 고르는 문제

백트레킹으로 해결

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int r, c;
int ret;
string line;
char mp[24][24];
vector<char> ret_temp;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
 
void dfs(int y, int x)
{
  ret_temp.push_back(mp[y][x]);
 
  for (int i = 0; i < 4; i++)
  {
    int ny = y + dy[i];
    int nx = x + dx[i];
    if (ny >= 0 && ny < r && nx >= 0 && nx < c)
    {
      if (find(ret_temp.begin(), ret_temp.end(), mp[ny][nx]) == ret_temp.end())
      {
        dfs(ny, nx);
        ret = max(ret, static_cast<int>(ret_temp.size()));
        ret_temp.pop_back();
      }
    }
  }
}
 
int main()
{
  cin >> r >> c;
  for (int i = 0; i < r; i++)
  {
    cin >> line;
    for (int j = 0; j < c; j++)
    {
      mp[i][j] = line[j];
    }
  }
 
  dfs(0, 0);
  ret = max(ret, static_cast<int>(ret_temp.size()));
  cout << ret;
}