[1일 1알고] 리틀 프렌즈 사천성

https://school.programmers.co.kr/learn/courses/30/lessons/1836

프로그래머스

 

사천성을 진행합니다.

일반적인 사천성 게임처럼 경로가 막혀있다면 타일을 제거할 수 없고 경로를 찾을 수 있다면 제거할 수 있습니다.

 

다만 해당 문제에서는 경로가 유턴처럼 꺾이는 방법은 불가하고, 오직 두 개 이하의 수평/수직 선분(ㅡ, ㄱ 혹은 ㄴ 형태)을 사용하는 방법만 가능합니다.

 

그리고 가능한 경로가 여러개라면, 알파벳이 가장 빠른 순서부터 찾는 것이 답입니다.

주어진 조건은 m, n이 100이하이며, 알파벳은 A~Z까지만 존재하기 때문에 어떤 방법으로 풀더라도 시간초과가 발생할 일은 없을 것입니다.

 

따라서 해결을 위해서는 가장 간단하면서도 효과적인 방법이 알파벳이 빠른 순서대로 가능한지를 계속해서 찾아가는 것이라고 생각했습니다.

---

탐색을 위해서 map을 사용한다고 생각이 들었는데 정렬된 순서가 필요하기 때문에 unordered_map이 아닌 그냥 map을 사용했습니다.

using namespace std;

// 사천성 진행
// 규칙 ->
// 경로의 양 끝은 제거하려는 두 타일
// 경로는 두 개 이하의 수평/수직 선분
// 경로 상 장애물은 없어야함
// 모든 타일을 제거할 수 있는지, 어떤 순서로 제거하면 되는지

// 해가 여러가지라면 알파벳 순으로 먼저인 문자열 return

// mxn크기의 2차원벡터, 같은 글자로 이루어진 타일은 항상 두 개씩만 존재함
vector<string> Board;

struct Tile
{
    vector<pair<int, int>> point;
    bool visited = false;
};

bool IsSafe(int r, int c)
{
    if (Board[r][c] == '.')
        return true;
    return false;
}

int GetStep(int from, int to)
{
    if (from < to)
        return 1;

    if (from > to)
        return -1;

    return 0;
}
bool CheckLine(int sr, int sc, int er, int ec, bool allowEnd)
{
    if (sr != er && sc != ec)
        return false;

    int r = sr;
    int c = sc;

    int rStep = GetStep(sr, er);
    int cStep = GetStep(sc, ec);

    while (r != er || c != ec)
    {
        r += rStep;
        c += cStep;

        if (r == er && c == ec && allowEnd == true)
            break;

        if (IsSafe(r, c) == false)
            return false;
    }

    return true;
}
bool canGo(int sr, int sc, int er, int ec)
{
    // 0번 꺾는 경우
    if (CheckLine(sr, sc, er, ec, true))
        return true;

    // 세로 먼저 이동 후 가로 이동
    if (CheckLine(sr, sc, er, sc, false) &&
        CheckLine(er, sc, er, ec, true))
    {
        return true;
    }

    // 가로 먼저 이동 후 세로 이동
    if (CheckLine(sr, sc, sr, ec, false) &&
        CheckLine(sr, ec, er, ec, true))
    {
        return true;
    }

    return false;
}

string solution(int m, int n, vector<string> board) {
    Board = board;
    string answer = "";
    map<char, Tile> tileMap;

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
                tileMap[board[i][j]].point.push_back({ i, j });
        }
    }
    bool IMPOSSIBLE = false;
    while (!tileMap.empty())
    {
        bool isPossible = false;
        for (auto& elem : tileMap)
        {
            int sr = elem.second.point[0].first;
            int sc = elem.second.point[0].second;
            int er = elem.second.point[1].first;
            int ec = elem.second.point[1].second;
            if (canGo(sr, sc, er, ec))
            {
                answer += elem.first;
                tileMap.erase(elem.first);
                isPossible = true;

                Board[sr][sc] = '.';
                Board[er][ec] = '.';
                break;
            }
        }
        if (!isPossible)
        {
            IMPOSSIBLE = true;
            break;
        }
    }

    if (IMPOSSIBLE)
        answer = "IMPOSSIBLE";
    return answer;
}

 

찾아야하는 경우는 0번 꺾는 경우, 1번 꺾는경우 (ㄱ, ㄴ) 입니다. 이 중 하나라도 가능하다면 삭제가 가능하고 

특정 타일을 삭제해서 뒤의 타일을 삭제할 수 없게 되는 경우는 발생하지 않기 때문에

알파벳순으로 계속해서 탐색해 제거한다면, 결국 가능한 경우 중 가장 빠른 경우를 얻을 수 있을 것입니다.