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

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

풀이 순서는 다음과 같다.

1. Board에 존재하는 알파벳이 무엇무엇 있는지 체크한다.

• set을 이용하여 중복제거를 통해 체크하고, row, col 위치를 기록해둔다.

2. 알파벳을 오름차순으로 정렬한다.

• 오름차순으로 정렬된 알파벳을 돌면서 문제 조건에 맞도록 tile을 지운다.
• 만약 지웠으면 해당 알파벳을 삭제하고, 알파벳의 맨 앞부터 다시 한다.
• 만약 정렬된 알파벳 끝까지 못지웠으면, IMPOSSIBLE인 케이스이다.

3. tile을 지우는 것은 bfs를 이용해서 한다.

• 단 꺽이는 횟수가 2번 이상이면 안되기 때문에, 꺽이는 횟수를 기록해둔다.
• 그 외의 것은 평범한 bfs 처럼 구현하면 된다.

next_permutation을 이용해서 풀었다가 계속 시간초과가 났다;
break를 걸어도 시간초과가 나는 것 보면 next_permutation 자체가 좀 비싼 것 같다.
되도록이면 사용을 지양하는게 좋은듯...

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;

typedef struct __pos {
    int row;
    int col;
    int curved;
    int dir;
} pos;
int rowDir[4];
int colDir[4];
pos tile_pos[26];
vector<string> copy_board;
bool pang(int m, int n, char tile)
{
    int row = tile_pos[tile - 'A'].row;
    int col = tile_pos[tile - 'A'].col;

    queue<pos> q;
    for(int i=0;i<4;i++) {
        int nrow = row + rowDir[i];
        int ncol = col + colDir[i];
        if(nrow < 0 || nrow >= m || ncol < 0 || ncol >= n)
            continue;
        if(copy_board[nrow][ncol] == '*')
            continue;
        if(copy_board[nrow][ncol] != '.' && copy_board[nrow][ncol] != tile)
            continue;
        q.push( {nrow, ncol, 0, i} );
    }
    
    while(1) {
        if(q.empty())
            break;
        
        pos cur = q.front(); q.pop();
        
        if(copy_board[cur.row][cur.col] == tile) {
            copy_board[row][col] = '.'; 
            copy_board[cur.row][cur.col] = '.';
            return true;
        }
        
        for(int i=0;i<4;i++) {
            pos npos;
            if(i == (cur.dir + 2) % 4) 
                continue;
            npos.row = cur.row + rowDir[i];
            npos.col = cur.col + colDir[i];
            if(npos.row < 0 || npos.row >= m || npos.col < 0 || npos.col >= n)
                continue;
            if(copy_board[npos.row][npos.col] == '*')
                continue;
            if(copy_board[npos.row][npos.col] != '.' && copy_board[npos.row][npos.col] != tile)
                continue;
            if(cur.dir == i) 
                q.push( { npos.row, npos.col, cur.curved, cur.dir });   
            else 
                if(cur.curved < 1)
                    q.push( { npos.row, npos.col, cur.curved + 1, i });
        }
    }
    return false;
}

string solution(int m, int n, vector<string> board) {
    string answer;
    
    rowDir[0] = -1; rowDir[1] = 0; rowDir[2] = 1; rowDir[3] = 0;
    colDir[0] = 0; colDir[1] = 1; colDir[2] = 0; colDir[3] = -1;
    copy_board = board;
    set<char> tile_set;
    
    for(int i=0;i<m;i++) 
        for(int j=0;j<n;j++) {
            if(board[i][j] == '.' || board[i][j] == '*')
                continue;
            tile_pos[board[i][j] - 'A'] = { i, j };
            tile_set.insert(board[i][j]);
        }
    
    vector<char> tile(tile_set.begin(), tile_set.end());    
    sort(tile.begin(), tile.end());
    
    bool keep = true;
    int remove_cnt = 0;
    int tile_len = tile.size();
    while(keep) {
        keep = false;
        for(int i=0;i<tile.size();i++) {
            if(pang(m, n, tile[i])) {
                answer += tile[i];
                remove_cnt++;
                keep = true;
                tile.erase(tile.begin() + i);
                break;
            }
        }
    }
    if(remove_cnt == tile_len)
        return answer;
    
    return "IMPOSSIBLE";
}