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

 

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

 

 

<전체적인 알고리즘>

 

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

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

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

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

 

<전체 코드>

#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;
}

 

 

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