백준 1987 알파벳(c++)

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

1987번: 알파벳

이 문제는 DFS + 백트래킹 문제입니다. 보자마자, DFS보다 백트래킹 먼저 생각했습니다. 왜냐하면, 모든 말이 지날 수 있는 최대 칸수를 구해야 하기 때문입니다. 그래서 DFS로 탐색하면서, 조사한 모든 경우의 수(말이 지날수 있는 모든 경우의 수)들 중 최댓값을 구해주면 됩니다.

<코드>

#include <iostream>
#include <algorithm>

using namespace std;

char board[21][21];
bool visited[26];



int mov[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int max_cnt = 0;
int r,c;
void dfs(int x,int y, int cnt)
{
    
    visited[board[x][y] - 'A'] = true;

    max_cnt = max(max_cnt, cnt);

    for(int i=0;i<4;i++)
    {
        int row = x + mov[i][0];
        int col = y + mov[i][1];

        if(row>=0 && col>=0 && row<r && col<c && !visited[board[row][col]-'A']
        )
        {
            visited[board[row][col]-'A'] = true;
            dfs(row, col, cnt+1);
            visited[board[row][col]-'A'] = false;
        }
    } 
}


int main()
{
    
    cin>>r>>c;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cin>>board[i][j];
        }
    }

    dfs(0,0,1);

    cout<<max_cnt<<'\n';
}

<백트래킹적 접근>

if(row>=0 && col>=0 && row<r && col<c && !visited[board[row][col]-'A'])
{
     visited[board[row][col]-'A'] = true;
     dfs(row, col, cnt+1);
     visited[board[row][col]-'A'] = false;
}

 

백트래킹 --> DFS 탐색을 하면서, 더 이상 탐색할 필요가 없으면 넘어가는 행위입니다. 

다음과 같이, 방문을 했다면 개수를 세 번째 인자(경우의 수)를 하나 늘려주고 DFS 탐색을 진행하는 방식입니다. 그리고 다시 말이 갔던 경로를 다시 갈 수 있으므로 boolean 타입 visited 변수를 false로 초기화해줘야 합니다.