백준 1987번 알파벳

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

DFS(Depth First Search) 알고리즘과 백트래킹 기법을 요구하는 문제였기 때문에 visited 배열을 사용하지 않아도 되는 문제였습니다.

대신, 문제 조건에 같은 알파벳이 적힌 칸을 두 번 지날 수 없다고 하였으므로 매개변수로 alphabet을 전달하여 비트마스킹 기법을 사용해야하는 문제였습니다.

저는 A를 (1 << 0) ~ Z를 (1 << 25)로 표현하였고 나머지는 기존 DFS 알고리즘을 사용하는 문제와 동일하게 풀었습니다!

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int MAX = 20;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int R, C;

int result;

string board[MAX];

 

void DFS(int y, int x, long long alphabet, int cnt)

{

        alphabet |= (1 << (board[y][x] - 'A')); //이미 밟은 알파벳 표시

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextY && nextY < R && 0 <= nextX && nextX < C) //범위 내에 있고

                         if (!(alphabet & (1 << (board[nextY][nextX] - 'A')))) //새로운 알파벳일 경우에만

                                 DFS(nextY, nextX, alphabet, cnt + 1); //DFS

        }

 

        result = max(result, cnt);

}

 

int main(void)

{

        cin >> R >> C;

 

        for (int i = 0; i < R; i++)

                 cin >> board[i];

 

        result = -1;

        DFS(0, 0, (long long)1 << 26, 1); //알파벳 A(0) ~ Z(25)

        cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~