[백준 1987번] 알파벳

문제 링크: https://www.acmicpc.net/problem/1987

1987번: 알파벳

<문제 풀이> DFS, 백트랙킹

DFS로 갈 수 있는 최장 거리를 구하면 되는데 방문한 좌표로 방문 체크를 하는게 아니라 알파벳 사용여부로 방문체크를  해야 된다.

visited[26];

->알파벳 'A' ~  'Z' 각각에 'A'를 빼주면 0 ~ 25의 값에 대응시킬 수 있다

 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <cmath>
#include <deque>
#include <cstdlib>
using namespace std;
 
char board[20][20];
 
int R, C;
 
bool visited[26]; // A ~ Z ( 0 ~ 25)
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int res = 1;
void dfs(int x, int y, int depth) {
    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || ny < 0 || nx >= R || ny >= C)continue;
        if (visited[board[nx][ny] - 'A'])continue;
        visited[board[nx][ny] - 'A'] = true;
        res = max(res, depth + 1);
        dfs(nx, ny, depth + 1);
        visited[board[nx][ny] - 'A'] = false;
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> board[i][j];
        }
    }
    visited[board[0][0] - 'A'] = true;
    dfs(0, 0, 1);
 
    cout << res;
    return 0;
}