프로그래머스 - 리틀 프렌즈 사천성
풀이 순서는 다음과 같다.
- Board에 존재하는 알파벳이 무엇무엇 있는지 체크한다.
- set을 이용하여 중복제거를 통해 체크하고, row, col 위치를 기록해둔다.
- 알파벳을 오름차순으로 정렬한다.
- 오름차순으로 정렬된 알파벳을 돌면서 문제 조건에 맞도록 tile을 지운다.
- 만약 지웠으면 해당 알파벳을 삭제하고, 알파벳의 맨 앞부터 다시 한다.
- 만약 정렬된 알파벳 끝까지 못지웠으면, IMPOSSIBLE인 케이스이다.
- 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";
}
Author And Source
이 문제에 관하여(프로그래머스 - 리틀 프렌즈 사천성), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gkak1121/프로그래머스-리틀-프렌즈-사천성저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)