백준 1987 - 알파벳 (C++)

 

 

그림을 보면, C->A로 갈 땐, A를 밟은 적이 없기 때문에 이동할 수 있지만, A->A로 갈 땐 이미 A를 밟은 적이 있기 때문에 A로 이동할 수 없다.

 

한 번 밟았던 알파벳을 다시 밟지 않고 상하좌우 4방향으로 이동할 때, 최대 몇 칸까지 이동할 수 있는지를 구하는 문제이다.

 

 

문제 풀이

 

이 문제는 간단한 DFS문제이다. 

기존에 배열의 좌표를 기준으로 하던 방문체크를 알파벳으로 바꿔주면 끝이다.

 

시작점인 (1, 1) 을 시작으로 상하좌우 4방향에 대해 DFS를 실행하고, 더이상 전진할 수 없을 때, 최대 이동 거리를 계속 갱신해주면 된다.

 

풀이 코드

int Height = 0;
int Width = 0;

std::vector<std::vector<char>> Board;
std::vector<bool> isVisit;

int MaxDist = 0;

std::vector<std::pair<int, int>> Dir = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

 

먼저, 배열의 가로, 세로를 저장할 변수를 선언하였다.

이후, 알파벳이 저장될 배열 Board와 방문체크를 위한 isVisit도 선언해주었다.

 

MaxDist는 최대 이동 거리를 저장할 변수이다.

DFS에서 더이상 이동할 수 없을 때 이동한 거리와 MaxDist중 더 큰 값으로 MaxDist를 계속 갱신할 것이다.

 

Dir은 DFS에서 상하좌우를 탐색하기 위한 벡터이다.

 

이후, 아래와 같이 입력을 받고 초기화 해주었다.

std::cin >> Height >> Width;

Board.resize(Height, std::vector<char>(Width));
isVisit.resize(26);

for (int i = 0; i < Height; i++)
{
    for (int j = 0; j < Width; j++)
    {
        std::cin >> Board[i][j];
    }
}

 

 

DFS함수는 아래와 같다.

void DFS(int _X, int _Y, int _Depth)
{
    char CurChar = Board[_Y][_X];
    isVisit[CurChar - 'A'] = true;

    bool CanGo = false;

    for (int i = 0; i < 4; i++)
    {
        int NextX = _X + Dir[i].first;
        int NextY = _Y + Dir[i].second;

        if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
        {
            continue;
        }

        char NextChar = Board[NextY][NextX];
        if (isVisit[NextChar - 'A'] == true)
        {
            continue;
        }

        CanGo = true;

        DFS(NextX, NextY, _Depth + 1);
    }

    isVisit[CurChar - 'A'] = false;

    if (CanGo == false)
    {
        MaxDist = std::max(MaxDist, _Depth);
    }
}

 

일반적인 DFS와 동일하다. 다만, 방문체크를 알파벳을 기준으로 하고 있다.

CanGo라는 불리언 변수를 만들어두고, DFS내부에서 상하좌우 4방향중 단 한쪽이라도 이동했다면 CanGo를 true로 만들어주었다. 만약 CanGo가 False라면, 더이상 이동할 수 없다는 의미이므로 MaxDist를 갱신해주었다.

 

std::cout << MaxDist;

return 0;

 

마지막에 MaxDist를 출력해주면 끝이다.

 

 

 

코드 전문

#include <iostream>
#include <vector>
#include <algorithm>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int Height = 0;
int Width = 0;

std::vector<std::vector<char>> Board;
std::vector<bool> isVisit;

int MaxDist = 0;

std::vector<std::pair<int, int>> Dir = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

void DFS(int _X, int _Y, int _Depth)
{
    char CurChar = Board[_Y][_X];
    isVisit[CurChar - 'A'] = true;

    bool CanGo = false;

    for (int i = 0; i < 4; i++)
    {
        int NextX = _X + Dir[i].first;
        int NextY = _Y + Dir[i].second;

        if (NextX < 0 || NextY < 0 || NextX >= Width || NextY >= Height)
        {
            continue;
        }

        char NextChar = Board[NextY][NextX];
        if (isVisit[NextChar - 'A'] == true)
        {
            continue;
        }

        CanGo = true;

        DFS(NextX, NextY, _Depth + 1);
    }

    isVisit[CurChar - 'A'] = false;

    if (CanGo == false)
    {
        MaxDist = std::max(MaxDist, _Depth);
    }
}

int main()
{
    Init();

    std::cin >> Height >> Width;

    Board.resize(Height, std::vector<char>(Width));
    isVisit.resize(26);

    for (int i = 0; i < Height; i++)
    {
        for (int j = 0; j < Width; j++)
        {
            std::cin >> Board[i][j];
        }
    }

    DFS(0, 0, 1);

    std::cout << MaxDist;

    return 0;
}