[백준 1987번] 알파벳

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

1987번: 알파벳

풀이)

각 상태에서 사용된 알파벳을 체크해주면서 dfs를 돌리면 해결되었다. 이미 왔던 곳은 usedAlphabet으로 체크가 되기 때문에 visited배열은 따로 만들지 않았다. 

#include <iostream>
using namespace std;

int R, C, usedAlphabet[26], ans = 0;
int dir_x[4] = {0, 0, 1, -1};
int dir_y[4] = {1, -1, 0, 0};
string board[21];

void dfs(int x, int y, int cnt)
{
    if (cnt > ans)
        ans = cnt;
    usedAlphabet[board[x][y] - 'A'] = 1;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir_x[i];
        int ny = y + dir_y[i];
        if (nx < 0 || ny < 0 || nx > R - 1 || ny > C - 1)
            continue;
        if (!usedAlphabet[board[nx][ny] - 'A'])
        {
            dfs(nx, ny, cnt + 1);
            usedAlphabet[board[nx][ny] - 'A'] = 0;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> R >> C;
    for (int i = 0; i < R; i++)
        cin >> board[i];
    dfs(0, 0, 1);
	cout << ans << "\n";
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!