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

 

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제의 사천성은 일반 사천성과 다르게 딱 한번만 방향을 꺾을 수 있다.

 

그리고 제한도 까다롭지 않기 때문에, A부터 Z까지 글자들의 위치를 저장해 뒀다.

A부터 Z까지의 글자를 찾을 때, x를 기준으로 먼저 찾고 없다면 y를 증가시켜서 찾는 식으로 찾았기 때문에 특정 글자 중 y가 더 작은게 먼저 저장되도록 코드를 짰다. (y가 같다면 x가 작은 게 먼저 저장된다)

 

이렇게 코드를 짤 경우 두 좌표를 크게 직선과 꺾인 경우로 나눌 수 있다.

 

예를 들어 A라는 문자가 저장된 위치가 a, b라고 하자. 

만약 a와 b의 y좌표가 같거나, x좌표가 같다면, 직선으로만 연결해 카드를 지울 수 있다.

(한번만 꺾을 수 있으므로 ㄷ자 모양이 불가능 하기 때문이다.)

 

만약 위 경우에 해당하지 않을 경우에는 두가지 경우가 있다.

a가 먼저 저장된 A의 위치라고 하면 a의 y좌표는 b보다 크거나 같게 된다.

그러므로 a와 b의 x좌표만 고려하면  a좌표를 기준으로 어떻게 이동할지를 결정 할 수 있게 된다.

 

만약 a의 x좌표가 b보다 큰 경우 

1. 왼쪽으로 이동했다가 y를 증가시키는 경우

2. y를 먼저 증가시키고 왼쪽으로 이동하는 경우

 

a의 x좌표가 b보다 작은 경우

1. 오른쪽으로 이동했다가 y를 증가시키는 경우

2. y를 먼저 증가시키고 오른쪽으로 이동하는 경우

 

이렇게 경우를 구분하고 나면 퍼즐을 다 제거할 수 있는지 확인하면 된다.

퍼즐을 제거할 수 있을 경우에 오름차순으로 정렬을 하라고 했으므로, A글자부터 제거가 가능한지 확인한다.

만약 제거가 가능하면, 그 글자를 제거하고 다시 A글자부터 제거가 가능한지 퍼즐을 확인하면 된다.

이렇게 퍼즐의 글자 개수만큼 반복을 돌리고 만약 제거가 불가능할 경우 IMPOSSIBLE을 return하면 된다.

 

​

[아이디어 정리]

1. 퍼즐의 위치들을 저장한다.
2. 퍼즐의 개수만큼 반복을 돌리면서 오름차순으로 제거가 가능한지 확인한다.
3. 글자의 위치를 비교하며 방법에 따라 제거가 가능한지 파악한다.
4. 만약 제거가 가능할 경우 글자를 제거하고, 다시 A부터 제거가 가능한지 파악한다.
5. 만약 A부터 Z사이의 글자 중 제거할 수 있는 글자가 없다면, IMPOSSIBLE를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <map>
using namespace std;

bool CanRemove(pair<int,int> a, pair<int,int> b, vector<vector<bool>> &board)
{
    // a가 더 위에 있다. 만약 a랑 b가 같은 줄 일 경우 a는 왼쪽에 있다.
    bool flag=false;
    if (a.second<b.second)
    {
        // 오른쪽 후 아래
        flag=true;
        for (int i=a.second+1; i<=b.second; i++)
        {
            if (!board[a.first][i])
            {
                flag=false;
                break;
            }
        }
        if (flag)
        {
            for (int i=a.first+1; i<b.first; i++)
            {
                if (!board[i][b.second])
                {
                    flag=false;
                    break;
                }
            }
            if (flag)
            {
                return true;
            }
        }
        // 아래 후 오른쪽
        flag=true;
        for (int i=a.first+1; i<=b.first; i++)
        {
            if (!board[i][a.second])
            {
                flag=false;
                break;
            }
        }
        if (flag)
        {
            for (int i=a.second+1; i<b.second; i++)
            {
                if (!board[b.first][i])
                {
                    flag=false;
                    break;
                }
            }
            if (flag)
            {
                return true;
            }
        }
        return false;
    }
    else
    {
        // 왼쪽 후 아래
        flag=true;
        for (int i=a.second-1; i>=b.second; i--)
        {
            if (!board[a.first][i])
            {
                flag=false;
                break;
            }
        }
        if (flag)
        {
            for (int i=a.first+1; i<b.first; i++)
            {
                if (!board[i][b.second])
                {
                    flag=false;
                    break;
                }
            }
            if (flag)
            {
                return true;
            }
        }
        // 아래 후 왼쪽
        flag=true;
        for (int i=a.first+1; i<=b.first; i++)
        {
            if (!board[i][a.second])
            {
                flag=false;
                break;
            }
        }
        if (flag)
        {
            for (int i=a.second-1; i>b.second; i--)
            {
                if (!board[b.first][i])
                {
                    flag=false;
                    break;
                }
            }
            if (flag)
            {
                return true;
            }
        }
        return false;
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {
    string answer = ""; //세로 m 가로n
    vector<vector<pair<int,int>>> alpha(26);
    vector<vector<bool>> realBoard(m,vector<bool>(n,false)); //false는 벽
    map<int,string> alphaMap;
    int ansCnt=0;
    for (int i=0; i<m; i++)
    {
        for (int j=0; j<n; j++)
        {
            if (board[i][j]=='.')
            {
                realBoard[i][j]=true;
            }
            else if(board[i][j]=='*')
            {
                continue;
            }
            else
            {
                ansCnt+=1;
                alpha[board[i][j]-'A'].push_back(make_pair(i,j));
                alphaMap[board[i][j]-'A']=board[i][j];
            }
        }
    }
    ansCnt/=2;
    bool flag2=false;
    for (int i=0; i<ansCnt; i++)
    {
        flag2=false;
        for (int j=0; j<26; j++)
        {
            if (alpha[j].size()>0)
            {
                if (CanRemove(alpha[j][0],alpha[j][1],realBoard))
                {
                    flag2=true;
                    realBoard[alpha[j][0].first][alpha[j][0].second]=true;
                    realBoard[alpha[j][1].first][alpha[j][1].second]=true;
                    alpha[j]=vector<pair<int,int>>(0);
                    answer+=alphaMap[j];
                    break;
                } 
            }                    
        }
        if (!flag2)
        {
            return "IMPOSSIBLE";
        }
    }
    return answer;
}

 

---

문제는 어렵지 않은데 구현이 생각보다 까다로웠던 문제였던 것 같다.

 

프로그래머스