프로그래머스 Lv2 리틀 프렌즈 사천성

이 문제는 bfs로 풀어야한다 생각은 했다.
1. map을 만들어서 각 케릭터에 대한 좌표 값을 모아둔다.
2. 타일이 모두 빌 때 까지 반복문을 돌리고, 반복문 안에서는 타일에 대해 순회한다.
이 때 타일을 한번 순회 했는데 한번도 케릭터를 제거하지 못하면 실패 처리한다.
3. 순회를 하는 코드는 케릭터의 시작 위치를 가져오고 
제일 먼저 4개의 주변 방향을 큐 안에 넣는다. 이 때 "위치, 이동 방향, 꺽은 적이 있는지"를 확인 할 수 있는 데이터를 같이 넣어준다.

#include <string>
#include <vector>
#include <queue>
#include <map>
#include <cstring>
#include <iostream>

using namespace std;

struct pos
{
    int m; //m 좌표
    int n; //n 좌표
    int r; //이동 방향
    bool turn; //꺾은 적이 있는지
    
    void init(int m, int n, int r, bool turn)
    {
        this->m = m;
        this->n = n;
        this->r = r;
        this->turn = turn;
    }
};

int M;
int N;
int d[] = {-1, 1, 0, 0};
bool visit[101][101][4];
map<char, vector<pair<int, int>>> tile;

bool in_range(int m, int n)
{
    if(m < 0 || m >= M || n < 0 || n >= N)
        return false;
    return true;
}

bool find_pair(char target, vector<string>& board)
{
    queue<pos> q;
    pos curr, next;
    int i, m, n;
    
    memset(visit, false, sizeof(visit));
    
    m = tile[target][0].first;
    n = tile[target][0].second;
    
    for(int i = 0; i < 4; ++i)
    {
        visit[m][n][i] = true;
        next.init(m + d[i], n + d[3 - i], i , false);
        if(!in_range(next.m, next.n))
        {
            continue;
        }
        q.push(next);
        visit[next.m][next.n][i] = true;
    }
    
    while(!q.empty())
    {
        curr = q.front();
        q.pop();
        
        if(board[curr.m][curr.n] == target)
        {
            board[m][n] = '.';
            board[curr.m][curr.n] = '.';
            return true;
        }
        
        if(board[curr.m][curr.n] != '.')
            continue;
        
        for(int i = 0; i < 4; ++i)
        {
            next.init(curr.m + d[i], curr.n + d[3 - i], i, curr.turn);
            
            if(curr.r != i)
            {
                if(curr.turn)
                    continue;
                next.turn = true;
            }
            
            if(!in_range(next.m, next.n) || visit[next.m][next.n][next.r])
                continue;
        
            q.push(next);
            visit[next.m][next.n][next.r] = true;
        }
    }
    return false;
}

void find(string& answer, vector<string>& board)
{
    char target;
    bool remove;
    
    while(!tile.empty())
    {
        remove = false;
        
        for(auto t : tile)
        {
            target = t.first;

            if(find_pair(target, board))
            {
                remove = true;
                answer += target;
                tile.erase(target);
                break;
            }
        }
        
        if(!remove)
        {
            answer = "IMPOSSIBLE";
            break;
        }
    }
}

void check_tile(vector<string>& board)
{
    int i, j;
    tile.clear();
    
    for(i = 0; i < M; ++i)
    {
        for(j = 0; j < N; ++j)
        {
            if(isalpha(board[i][j]))
            {
                tile[board[i][j]].push_back(make_pair(i,j));
            }
        }   
    }
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {
    string answer = "";
    M = m;
    N = n;
    check_tile(board);
    find(answer, board);
    return answer;
}