[C++]2017 카카오코드 본선 리틀 프렌즈 사천성(프로그래머스 3레벨)

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int iVisit[100][100] = {};
 
void DFS(int iX, int iY, int iFirstX, int iFirstY,
    vector<string>& board, int iBendCount, char cDest, vector<pair<char, pair<int, int>>>& sAnswer)
{
    // 꺽인 횟수가 2가 넘으면 실패
    if (iBendCount >= 2)
        return;
 
    if (iX < board.size())
    {
        if (iY < board[iX].size())
        {
            // 목적지거나 본인이 아닐 때
            if (!iVisit[iX][iY] && board[iX][iY] == cDest && (iFirstX != iX || iFirstY != iY))
                sAnswer.push_back({ board[iX][iY], {iX, iY} });
 
            // 갈 수 있거나 본인일 때
            else if (!iVisit[iX][iY] && (board[iX][iY] == '.' || board[iX][iY] == cDest))
            {
                iVisit[iX][iY] += 1;
 
                // 처음 입력할 때
                if (!iBendCount)
                {
                    // 사방으로 찾아간다.
                    DFS(iX + 1, iY, iX, iY, board, iBendCount + 1, cDest, sAnswer);
                    DFS(iX, iY + 1, iX, iY, board, iBendCount + 1, cDest, sAnswer);
                    DFS(iX - 1, iY, iX, iY, board, iBendCount + 1, cDest, sAnswer);
                    DFS(iX, iY - 1, iX, iY, board, iBendCount + 1, cDest, sAnswer);
                }
 
                // 처음이 아닐 때
                else
                {
                    // 기본 입력과 이전 위치의 차이
                    int iNextX = iX - iFirstX;
                    int iNextY = iY - iFirstY;
 
                    // X 쪽 이동일 경우
                    if (iNextX && iBendCount == 1)
                    {
                        // 꺽이지 않는 X방향으로 다시 입력 (본인쪽으로는 다시 이동할 필요 X)
                        DFS(iX + iNextX, iY, iX, iY, board, iBendCount, cDest, sAnswer);
 
                        // 꺽인 Y방향 두 곳으로 입력
                        DFS(iX, iY + 1, iX, iY, board, iBendCount + 1, cDest, sAnswer);
                        DFS(iX, iY - 1, iX, iY, board, iBendCount + 1, cDest, sAnswer);
                    }
 
                    //Y 축 이동일 경우
                    else if (iNextY && iBendCount == 1)
                    {
 
                        // 꺽이지 않는 Y방향으로 다시 입력 (본인쪽으로는 다시 이동할 필요 X)
                        DFS(iX, iY + iNextY, iX, iY, board, iBendCount, cDest, sAnswer);
 
                        // 꺽인 X방향 두 곳으로 입력
                        DFS(iX + 1, iY, iX, iY, board, iBendCount, cDest, sAnswer);
                        DFS(iX - 1, iY, iX, iY, board, iBendCount, cDest, sAnswer);
                    }
 
                    // X축 이동 + 이미 두 번째 꺽였을 경우 그 쪽 방향으로만 이동
                    else if (iNextX)
                        DFS(iX + iNextX, iY, iX, iY, board, iBendCount, cDest, sAnswer);
 
                    // Y축 이동 + 이미 두 번째 꺽였을 경우 그 쪽 방향으로만 이동
                    else if (iNextY)
                        DFS(iX, iY + iNextY, iX, iY, board, iBendCount, cDest, sAnswer);
                }
            }
 
            else
                return;
        }
        else
            return;
    }
    else
        return;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
// m -> size 
// n -> board[i].size()
string solution(int m, int n, vector<string> board)
{
    string answer = "";
    vector<char> vecAnswer = {};
    vector<pair<char, pair<int, int>>> vecPair = {};
    char cAnswer = 'A' - 1;
 
    while (cAnswer != 'Z' + 1)
    {
        // A부터 늘려가면서 검사
        ++cAnswer;
 
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[i].size(); ++j)
            {
                if (board[i][j] == cAnswer)
                {
                    int iPairSize = vecPair.size();
 
                    // 시작하기 전에 Visit 초기화
                    memset(iVisit, 0, sizeof(iVisit));
 
                    // 전체 검색
                    DFS(i, j, i, j, board, 0, board[i][j], vecPair);
 
                    // 사이즈가 다르다면 추가했다는 뜻이기 때문에 입력
                    if (iPairSize < vecPair.size())
                        vecPair.push_back({ board[i][j], {i,j} });
                }
            }
        }
 
        // vecPair의 사이즈가 있다는 것은 찾았다 -> A부터 다시 검색
        if (vecPair.size())
            cAnswer = 'A' - 1;
 
        while (vecPair.size())
        {
            pair<char, pair<int, int>> pPair = vecPair.back();
            vecPair.pop_back();
 
            // 찾은 영어 입력
            vecAnswer.push_back(pPair.first);
 
            // 찾은 곳 삭제
            board[pPair.second.first][pPair.second.second] = '.';
        }
    }
 
    for (int i = 0; i < board.size(); ++i)
    {
        for (int j = 0; j < board[i].size(); ++j)
        {
            // A ~ Z 사이가 있다는 것은 게임을 끝내지 못했다는 뜻 -> 불가능
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
                return"IMPOSSIBLE";
        }
    }
 
    // 똑같은 것들을 다 넣었기 때문에 unique로 실행
    vecAnswer.erase(unique(vecAnswer.begin(), vecAnswer.end()), vecAnswer.end());
 
    for (int i = 0; i < vecAnswer.size(); ++i)
    {
        answer.push_back(vecAnswer[i]);
    }
 
    if (answer.size())
        return answer;
    else
        return "IMPOSSIBLE";
}

솔직히 어려운 것보다.. 그냥 뭔가 좀... 귀찮았다고 해야하나 짜증난다고 해야할까...

생각보다 어렵진 않았고 걍 모든 경로를 검사해야되고 A부터 다시 시작해야 한다! 이부분이 좀 어려웠다.