[Algorithm] Programmers :: 리틀 프렌즈 사천성

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

프로그래머스

struct Node
{
    char tile;
    int y = -1;
    int x = -1;
};
 
vector<string> boardMap;
string tempAnswer;
string answer;
int answerCount = 0;
bool isBreak = false;
 
 
vector<vector<Node>> nodesInfo(26);
vector<int> curTiles;
bool checkTiles[26] = { false };
 
 
bool Check(const Node& a, const Node& b)
{
    int yGap = b.y - a.y;
    int xGap = abs(b.x - a.x);
    int isMinus = 1;
 
    if (b.x - a.x < 0)
    {
        isMinus = -1;
    }
 
    bool isRowColumnCheck = true;
 
    // 행,열 검사.
    
    for (int i = 1; i <= yGap; ++i) // 행검사.
    {
        if (boardMap[a.y + i][a.x] == a.tile)
        {
            return true;
        }
        else if (boardMap[a.y + i][a.x] == '.') continue;
        else // 장애물 있으면, 다른 타일이나 '*'
        {
            isRowColumnCheck = false;
            break;
        }
    }
 
    if (isRowColumnCheck) // 행검사는 통과. 열검사.
    {
        for (int i = 1; i <= xGap; ++i) // 행,열검사에서 열검사.
        {
            if (boardMap[a.y + yGap][a.x + i * isMinus] == a.tile)
            {
                return true;
            }
            else if (boardMap[a.y + yGap][a.x + i * isMinus] == '.') continue;
            else
            {
                isRowColumnCheck = false;
                break;
            }
        }
    }
    
    if (!isRowColumnCheck)// 행,열은 실패. 열,행 검사.
    {
        for (int i = 1; i <= xGap; ++i) // 열,행검사에서 열검사.
        {
            if (boardMap[a.y][a.x + i * isMinus] == a.tile)
            {
                return true;
            }
            else if (boardMap[a.y][a.x + i * isMinus] == '.') continue;
            else return false;
        }
 
        for (int i = 1; i <= yGap; ++i) // 열,행검사에서 행검사.
        {
            if (boardMap[a.y + i][a.x + xGap * isMinus] == a.tile)
            {
                return true;
            }
            else if (boardMap[a.y + i][a.x + xGap * isMinus] == '.') continue;
            else return false;
        }
    }
}
 
 
void DFS(int tilesAscii, int count)
{
    if (isBreak) return;
 
    if (count == answerCount)
    {
        answer = tempAnswer;
        isBreak = true;
        return;
    }
 
    for (int i = 0; i < curTiles.size(); ++i)
    {
        if (checkTiles[curTiles[i]]) continue; // 빈곳은 제외
 
        if (!Check(nodesInfo[curTiles[i]][0], nodesInfo[curTiles[i]][1])) continue;
 
        checkTiles[curTiles[i]] = true;
        tempAnswer.push_back(curTiles[i] + 65);
        boardMap[nodesInfo[curTiles[i]][0].y][nodesInfo[curTiles[i]][0].x] = '.';
        boardMap[nodesInfo[curTiles[i]][1].y][nodesInfo[curTiles[i]][1].x] = '.';
 
        DFS(curTiles[i], count+1);
 
        checkTiles[curTiles[i]] = false;
        tempAnswer.pop_back();
        boardMap[nodesInfo[curTiles[i]][0].y][nodesInfo[curTiles[i]][0].x] = curTiles[i];
        boardMap[nodesInfo[curTiles[i]][1].y][nodesInfo[curTiles[i]][1].x] = curTiles[i];
    }
}
 
 
string solution(int row, int column, vector<string> board)
{
    boardMap.clear();
    boardMap = board;
    tempAnswer = "";
    answer = "";
    answerCount = 0;
    isBreak = false;
 
    nodesInfo.clear();
    nodesInfo.resize(26);
    curTiles.clear();
    memset(checkTiles, false, sizeof(checkTiles));
 
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < column; ++j)
        {
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
            {
                if (nodesInfo[board[i][j] - 'A'].size() == 0)
                {
                    curTiles.push_back(board[i][j] - 65);
                }
 
                nodesInfo[board[i][j] - 65].push_back({board[i][j], i,j });
 
                ++answerCount;
            }
        }
    }
 
    sort(curTiles.begin(), curTiles.end());
    answerCount /= 2;
 
    for (int i = 0; i < curTiles.size(); ++i)
    {
        if (!Check(nodesInfo[curTiles[i]][0], nodesInfo[curTiles[i]][1])) continue;
 
        checkTiles[curTiles[i]] = true;
        tempAnswer.push_back(curTiles[i] + 65);
        boardMap[nodesInfo[curTiles[i]][0].y][nodesInfo[curTiles[i]][0].x] = '.';
        boardMap[nodesInfo[curTiles[i]][1].y][nodesInfo[curTiles[i]][1].x] = '.';
 
        DFS(curTiles[i], 1);
 
        checkTiles[curTiles[i]] = false;
        tempAnswer.pop_back();
        boardMap[nodesInfo[curTiles[i]][0].y][nodesInfo[curTiles[i]][0].x] = curTiles[i];
        boardMap[nodesInfo[curTiles[i]][1].y][nodesInfo[curTiles[i]][1].x] = curTiles[i];
    }
 
    if (answer.size() != answerCount) return "IMPOSSIBLE";
    return answer;
}

 

이 문제는 무엇보다도 제일 중요한건, 반드시 전역변수를 solution내에서 다 재정의해줘야 한다.

vector로 했든 뭘로했든, 반드시 재정의 해야한다.

vector하나 재정의 안한거 때문에 통과를 못해서 시간 좀 날렸다. 반드시 모두 다 재정의해주자.

 

처음 주어지는 정보들로 각 알파벳 쌍의 위치를 따로 보관한다음, 백트래킹을 수행한다.

퍼즐을 클리어할 수 있는 경로가 여러개일 때, 알파벳순으로 출력하라했기 때문에 애초에 백트래킹을 알파벳순으로 수행해버린 후, 조건에 맞을때 return 시키면 된다. 굳이 모든 경우의 수를 구할필요가 절대 없다.

알파벳순으로 수행하기위해 처음에 주어지는 맵정보를 가공해서 이쁘게 알파벳순으로 저장해놓자.

 

이후 주어지는 알파벳쌍이 연결되는지를 검사하는데, 다른 사람같은 경우 뭔가 획기적인 그런게 있는지는 모르겠지만

나같은 경우는 그냥 생각나는대로 구현했다.

 

크게 총 두번의 검사를 한다.

 

행 검사 -> 열 검사 후, 실패한다면

열 검사->행 검사   를 한다.

 

어려울 건 없고, 맵데이터 특성상 뒤에 나타나는 알파벳같은 경우는 앞의 알파벳보다 무조건 y값이 크기때문에 yGap은 반드시 0이상이다.

다만, x값은 뒤에 나타나더라도 앞에 나타나는 것보다 더 작을 수 있기 때문에 이부분에 대한 예외처리를 해줘야 한다.