[BOJ] 1987번 알파벳

BOJ 1987번 알파벳

보자마자 그래프 전체 탐색이라고 생각했다. bfs 혹은 dfs를 사용하면 된다.
처음에 시간초과가 뜨길래 재귀 때문에 그런가하고 살펴보다가 혹시 하는 마음에 vector를 배열로 바꾸니 성공했다. 벡터의 함수들을 꼭 사용해야 할 때가 아니라면 배열을 사용하는 게 좋을 듯 하다.

#include <iostream>
using namespace std;

#define ASCII_A 65

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int answer;
char board[22][22];
bool alphabet[26];

void dfs(int i, int j, int depth) {
  if(depth > answer) answer = depth;

  for(int k = 0;k<4;k++){
    if(board[i+dx[k]][j+dy[k]] && !alphabet[board[i+dx[k]][j+dy[k]]-ASCII_A]) {
      alphabet[board[i+dx[k]][j+dy[k]]-ASCII_A] = true;
      dfs(i+dx[k], j+dy[k], depth+1);
      alphabet[board[i+dx[k]][j+dy[k]]-ASCII_A] = false;
    }
  }
}

int main() {
  int R, C;
  cin>> R>>C;

  for(int i=1;i<=R;i++){
    for(int j=1;j<=C;j++){
      cin>>board[i][j];
    }
  }

  alphabet[board[1][1]-ASCII_A] = true;
  dfs(1, 1, 1);
  cout<<answer;

  return 0;
}

시간 복잡도