[백준 1987] 알파벳

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

1987번: 알파벳

최근에 공채가 뜨는 기업들이 생겨서 준비를 하느라 블로그에 글을 올릴 여유가 없다보니 소훌해지는 것 같습니다.

블로그를 죽이지 말자는 마음가짐으로 최근에 푼 문제중 쉬운 문제를 리뷰해보려고 합니다.

백준 1987 알파벳입니다.

 

R*C의 2차원 배열이 있고 시작점은 좌측 최상단입니다.

이 때 상,화,좌,우 각 한칸씩 진행할 수 있을 때 밞지 않은 알파벳만을 밞아서 최대한 많이 밞은 횟수를 출력하면 됩니다.

전형적인 DFS를 이용한 백트래킹 문제입니다. 

 

DFS를 돌면서 모든 경우를 해보면 되는데 이 때 백트래킹을 위한 가지치기는 다음 발판이 밞음 이력 유무가 됩니다.

보통 DFS의 경우 방문한 칸을 중복방문하지 않기 위해 이미 밞은 칸을 방문체크합니다.

그러나 이 문제는 (밞았다 == 이미 사용한 알파벳) 이다가 되므로 알파벳 방문 체크만 하고 인덱스 방문 체크는 하지 않아도 됩니다.

 

기본적인 DFS는 기존의 DFS와 같이

(알파벳 방문 체크 ->DFS를 통한 함수 재귀 -> 재귀한 함수 리턴 후 방문 체크 해제)

이런 방식으로 진행하게 됩니다.

 

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int R,C,dy[4]={-1,0,1,0},dx[4]={0,1,0,-1},mx=1;
char mat[30][30];
int check[30];

void DFS(int y, int x,int n)
{
    for(int i=0;i<4;i++)
    {
        int ny = y+dy[i], nx=x+dx[i];
        if(ny<0 || nx<0 || ny >= R || nx >= C || check[mat[ny][nx]-'A']) continue;
        mx = max(mx,n+1); check[mat[ny][nx]-'A']=1; if(mx==26) return;
        DFS(ny,nx,n+1);
        check[mat[ny][nx]-'A']=0;
    }
}
int main()
{
    ios::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 >> mat[i][j];
        }
    }
    check[mat[0][0]-'A']=1;
    DFS(0,0,1);
    cout << mx;


}

 매우 간단한 문제입니다.

solved.ac 기준으로 골드3이 측정되어있지만 더 낮은 난이도를 부여해도 될 것 같습니다.