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

 

문제 링크 : programmers.co.kr/learn/courses/30/lessons/1836#

 

 

<전체적인 알고리즘>

 

1. 존재하는 알파벳과 알파벳의 위치를 map에 저장한다. 

2. map은 자동 오름차순 정렬이 되니 차례대로 탐색하며 제거가능한 알파벳이 있나 확인

   - 알파벳 제거하는 알고리즘은 백트래킹이나 bfs쓰면 된다. (자세한 알고리즘은 코드의 주석 참고)

3. 전부 제거하거나 더이상 제거 못할때 까지 2를 반복 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117

#include<iostream> #include <string> #include <vector> #include<queue> #include<map> #include<algorithm>   using namespace std;   int m; int n; vector<string> board; bool check[102][102]; int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}; map<char,pair<int,int>> pos; map<char,pair<int,int>>::iterator iter; class ins {     public:     int x,y,turn_count,d;     ins(int x, int y, int turn_count,int d)     {         this->x=x;         this->y=y;         this->turn_count=turn_count;         this->d=d;     } };   vector<int> bfs(int startx, int starty)   //제거 가능한 타일 목적지 위치 반환 {     fill(&check[0][0], &check[99][100], 3);     char alpha = board[startx][starty];       queue<ins> q;     q.push(ins(startx, starty, 0, -1));     check[startx][starty] = 0;     bool isfirst = true;     while (!q.empty())     {         int x = q.front().x;         int y = q.front().y;         int turn_count = q.front().turn_count;  //꺾은 횟수         int d = q.front().d;  //현재 진행방향         q.pop();                   if (!isfirst&&board[x][y] == alpha)  // 목적지 알파벳 찾으면 반환         {             vector<int> v{ x,y };             return v;         }         isfirst = false;                   for (int dd = 0; dd < 4; dd++)         {             int tmp = turn_count;             int nextx = x + dir[dd][0];             int nexty = y + dir[dd][1];             if (nextx < 0 || nexty < 0 || nextx >= m || nexty >= n)continue;                if (!(board[nextx][nexty]=='.'||board[nextx][nexty]==alpha))continue;             if (d != -1 && d != dd) tmp++;  //꺾으면 tmp증가               if (tmp > 1)continue;  //2번이상 꺾으면 패스               if (check[nextx][nexty]<tmp)continue;             check[nextx][nexty] = tmp;             q.push(ins(nextx, nexty, tmp, dd));         }     }     vector<int> v;     return  v; }   // 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요. string solution(int m2, int n2, vector<string> board2) {           m=m2;     n=n2;     board=board2;           for(int i=0;i<m;i++)     {         for(int j=0;j<n;j++)         {             if(board[i][j]>='A'&&board[i][j]<='Z')             {                 char c = board[i][j];                 pos[c]=make_pair(i,j);   //map에 알파벳 위치 저장             }         }     }          string answer = "";     while(1)     {                     bool isfinish=true;         for(iter=pos.begin();iter!=pos.end();iter++)   //존재하는 알파벳순으로 확인하기         {             pair<int,int> p = iter->second;             vector<int> v = bfs(p.first,p.second);   //목적지 위치 반환                           if(v.size()==0)continue;  //벡터가 비어있으면 제거 불가능               isfinish=false;                           char c = board[p.first][p.second];             answer+=c;             board[p.first][p.second]='.';   //시작위치 알파벳 제거             board[v[0]][v[1]]='.';     //목적지 위치 알파벳 제거             pos.erase(iter);    // 제거했으니 map에서도 제거             break;         }           if(pos.size()==0)break;  //전부 제거했으면 종료         if(isfinish)return "IMPOSSIBLE";  //더이상 제거 안되면 impossible반환     }     return answer; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.