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

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

1987번: 알파벳

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int R, C, result = 0;
char board[20][20]; //보드
bool visited[26]; //알파벳 방문 여부 체크

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(int x, int y, int cnt)
{
    result = max(result, cnt);

    for(int i=0; i<4; i++) //4칸 중 한칸으로 이동
    {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || ny < 0 || nx >=C || ny >=R) continue;
        if(!visited[board[ny][nx] - 'A']) //해당 알파벳이 처음이면
        {
            visited[board[ny][nx] -'A'] = 1; //방문처리
            dfs(nx, ny, cnt+1); //현재 좌표와 카운트+1 넘김
            visited[board[ny][nx] -'A'] = 0; //백트래킹
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    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'] = 1; //첫 좌표 방문처리
    dfs(0, 0, 1); //첫 위치 전달 (카운트 1 시작)
    cout << result;
    
    return 0;
}

dfs와 백트래킹을 섞은 문제이다.

 

한번 갔던 알파벳을 다시 가면 안되므로, 각 알파벳마다 방문처리를 해줘야한다.

알파벳의 갯수가 26개이므로 사이즈 26의 bool 배열을 선언해주고 해당값 - 'A'를 해줘서 int 값으로 변환 후 해당 위치를 방문처리 해주면 된다.

 

그리고 4방향으로 이동이 가능하므로 dx, dy 배열을 선언해서 4방향으로 이동하며 탐색을 해주도록 하고, 범위 조건을 세워서 올바른 범위안에서만 동작하도록 해준다.

이후 현재 알파벳이 처음이라면 방문처리를 해준후 dfs를 돌리고 탐색을 진행하고, 다른 루트를 통해 현재 값을 지나가는 방법도 존재할 수 있으므로 백트래킹으로 dfs 이후에 방문처리 했던 값을 다시 되돌려준다.

 

이렇게 탐색을 돌려가며 조건에 맞으면 카운팅이 늘어나는데 이때 최대값을 따로 저장해서 출력해준다.