[BFS+DP] 프로그래머스 리틀 프렌즈 사천성 C++

 

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

프로그래머스

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

using namespace std;

struct pos {
    int x, y;
};

int M, N;
vector<string> Board;

bool bfs(char alp, pos p) {
    int dx[4] = {0, 1, 0, -1}; // 상우하좌
    int dy[4] = {-1, 0, 1, 0};
    
    int turn[M][N]; // 방향 꺾기 최소 횟수
    fill(&turn[0][0], &turn[M-1][N], 2); // INF로 초기화
    
    queue<vector<int>> q;
    q.push({p.x, p.y, -1}); // 이전 방향
    turn[p.y][p.x] = 0; // 초기화
    while(!q.empty()) {
        vector<int> now = q.front();
        q.pop();
        
        if (Board[now[1]][now[0]] == alp) {
            if ((now[0] != p.x) || (now[1] != p.y)) { // 같은 알파벳 타일 찾음(출발지X)
                Board[p.y][p.x] = '.';// 보드 수정
                Board[now[1]][now[0]] = '.';
                return true;
            }
        }

        for(int i=0; i<4; i++) {
            int newX = now[0] + dx[i];
            int newY = now[1] + dy[i];
            int dir = now[2];
            int cnt = turn[now[1]][now[0]];
            
            if ((newX < 0) || (newY < 0) || (newX >= N) || (newY >= M)) continue;
            if ((Board[newY][newX] != '.') && (Board[newY][newX] != alp)) continue;
            
            if ((dir != -1) && (i != dir)) cnt++; // 방향 꺾기
            if (cnt > 1) continue; // 방향 꺾기 2회 이상
            if (turn[newY][newX] >= cnt) { // DP 필요
                q.push({newX, newY, i});
                turn[newY][newX] = cnt;
            }
        }
    }
    return false;
}

string solution(int m, int n, vector<string> board) {
    M = m;
    N = n;
    Board = board;
    map<char, pos> mp; // 알파벳 -> 위치

    // 알파벳 -> 위치
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if ((board[i][j] != '.') && (board[i][j] != '*')) mp[board[i][j]] = {j, i};
        }
    }
    
    string answer = "";
    while(true) {
        bool isPossible = false;
        for(auto m : mp) { // 카드 알파벳 순서대로 확인 반복
            if (bfs(m.first, m.second)) {
                isPossible = true;
                answer += m.first;
                mp.erase(m.first);
                break;
            }
        }
        
        if (isPossible) continue;
        if (mp.empty()) return answer;
        else return "IMPOSSIBLE";
    }
}