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

https://school.programmers.co.kr/learn/courses/30/lessons/1836

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

 

[문제 요약]

- 리틀 프렌즈 사천성은 프렌즈 사천성과 유사한 게임이다. 게임은 2차원 배열에서 진행되는데, 여러 가지 무늬로 구성된 타일이 배치되어 있으며 같은 모양의 타일은 두 개씩 배치되어 있다. 게임의 목적은 배치된 모든 타일을 제거하는 것으로, 같은 모양의 타일을 규칙에 따라 제거하면 된다. 타일을 제거할 수 있는 경우는 다음과 같다.

 

- 다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.

• 경로의 양 끝은 제거하려는 두 타일이다.
• 경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다. (즉, 경로를 한 번 이하로 꺾을 수 있다)
  • 참고: 프렌즈 사천성은 경로가 세 개 이하의 선분으로 구성되어야 한다는 점이 다르다. (즉, 경로를 두 번 이하로 꺾을 수 있다)
• 경로 상에는 다른 타일 또는 장애물이 없어야 한다.

- 위의 배열에서 어피치 타일은 직선의 경로로 이을 수 있으므로 제거 가능하다. 라이언 타일 역시 한 번 꺾인 경로로 연결되므로 제거 가능하다. 무지 타일의 경우 다른 타일을 지나지 않는 경로는 두 번 꺾여야 하므로 제거할 수 없는 타일이며, 튜브 타일 역시 직선의 경로 사이에 장애물이 있으므로 제거 가능하지 않다.

 

- 타일 배열이 주어졌을 때, 규칙에 따라 타일을 모두 제거할 수 있는지, 그 경우 어떤 순서로 타일을 제거하면 되는지 구하는 프로그램을 작성해보자.

 

[문제 조건]

 

입력은 게임판의 크기를 나타내는 m과 n, 그리고 배치된 타일의 정보를 담은 문자열 배열 board로 주어진다. 이 배열의 크기는 m이며, 각각의 원소는 n글자의 문자열로 구성되어 있다. 입력되는 값의 제한조건은 다음과 같다.

• 1 <= m, n <= 100
• board의 원소는 아래 나열된 문자로 구성된 문자열이다. 각 문자의 의미는 다음과 같다.
  • .: 빈칸을 나타낸다.
  • *: 막힌 칸을 나타낸다.
  • 알파벳 대문자(A-Z): 타일을 나타낸다. 이 문제에서, 같은 글자로 이루어진 타일은 한 테스트 케이스에 항상 두 개씩만 존재한다.
  • board에는 알파벳 대문자가 항상 존재한다. 즉, 타일이 없는 입력은 주어지지 않는다.

[문제 풀이]

일단 문제가 요구하는 바는 생각보다 간단하다.

 

주어지는 타일에 대한 정보를 통해 규칙에 따라 타일들을 제거할 수 있는지? 만약에 제거 할 수 있다면 오름차순으로 제거하는 순서를 출력하고, 만약 모두 제거가 불가능하다면 IMPOSSIBLE을 출력하면 된다.

 

필자는 다음과 같은 순서로 문제를 해결했다.

• 주어지는 타일정보를 통해 지워야하는 타일들의 종류별로 2개의 좌표를 dt배열에 추가한다.
  • 이때 좌표는 행을 기준으로 오름차순으로 정렬한다.
  • 추가적으로 또 다른 배열(Dummy)에 타일들의 종류에 대한 정보를 오름차순으로 정렬해서 저장한다.
• Dummy배열을 순차적으로 확인하면서 해당하는 타일을 지울 수 있는지 판단하고, 지울 수 없다면 다음 타일로 넘어간다. 하지만 지울 수 있다면 answer에 타일 정보를 추가하고 남은 타일에 대하여 다시 처음부터 확인하면 지울 수 있는지 없는지 확인한다. 
• 만약 Dummy배열을 확인하면서 모든 타일에 대해 지울 수 없다면 IMPOSSIBLE을 출력한다.

이때 타일의 삭제 여부를 판단하는 과정을 알아보자.

타일이 위치하는 경우는 크게 3가지로 나눌 수 있다.

• 행의 위치가 같은 경우
• 열의 위치가 같은 경우
• 행과 열 모두 겹치는 같은 경우가 없이 대각선에 위치하는 경우

먼저 행과 열의 위치가 같은 경우들은 사이가 모두 빈칸인지만 확인하면 된다.

색칠된 타일들이 행 또는 열이 같은 타일들이다. 

if(a.first == b.first)
{
    for(int i=min(a.second,b.second)+1; i<max(a.second,b.second); i++)
        if(board[a.first][i] != '.') return false;
    return true;
}
else if(a.second == b.second)
{
    for(int i=min(a.first,b.first)+1; i<max(a.first,b.first); i++)
        if(board[i][a.second] != '.') return false;
    return true;
}

a와 b의 자료형은 pair<int,int> 이다.

 

세 번째 경우는 타일이 서로 대각선에 위치하는 경우인데, 이때 타일을 삭제 할 수 있는지 판단을 하려면 2개의 경로를 확인해야 한다.

 

다음과 같이 빨간색 화살표 경로와, 주황색 화살표 경로 둘 중에 하나라도 모두 빈 칸인 경로가 존재하면 그 타일을 지울 수 있는 타일이다.

 

이때 위쪽의 있는 I타일이 밑에 있는 I타일 보다 왼쪽에 위치할 수 있는 경우가 있기 때문에 필자는 두 경우를 나눠 생각했다.

if(a.second < b.second)
{
    bool 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; i<b.second; i++)
            if(board[b.first][i] != '.') {flag=false; break;}
        if(flag) return true;
    }

    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; i<b.first; i++)
            if(board[i][b.second] != '.') {flag= false; break;}
        if(flag) return true;
        else return false;
    }
    else return false;
}
else
{
    bool 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=b.second+1; i<=a.second; i++)
            if(board[b.first][i] != '.') {flag=false; break;}
        if(flag) return true;
    }

    flag = true;
    for(int i=b.second; i<a.second; i++)
        if(board[a.first][i] != '.') {flag = false; break;}

    if(flag)
    {
        for(int i=a.first; i<b.first; i++)
            if(board[i][b.second] != '.') {flag = false; break;}
        if(flag) return true;
        else return false;
    }
    else return false;
}

 

 

위 과정을 앞서 만들어 두었던 Dummy배열을 순차적으로 확인하면서 지울 수 있는 타일이 있는지 확인하고, 있다면 그 타일의 종류를 answer에 추가 후 Dummy배열의 앞에서 부터 다시 확인하고, 만약 지울 수 있는 타일이 Dummy배열에 없다면 IMPOSSIBLE을 리턴 시켜주면 된다.

while(1)
{
    vector<char> tmp;
    bool change = false;
    for(int i=0; i<dummy.size(); i++)
    {
        char cur = dummy[i];

        if(isPossible(dt[cur-'A'][0], dt[cur-'A'][1], board))
        {
            change = true;
            answer.push_back(cur); 
            board[dt[cur-'A'][0].first][dt[cur-'A'][0].second] = '.';
            board[dt[cur-'A'][1].first][dt[cur-'A'][1].second] = '.';

            for(int j=i+1; j<dummy.size(); j++) tmp.push_back(dummy[j]);
            break;
        }
        else tmp.push_back(cur);
    }

    if(!change) {answer="IMPOSSIBLE"; break;}
    sort(tmp.begin(), tmp.end());
    dummy = tmp;
    if(dummy.size() == 0) break;
}

 

 

[전체 소스 코드]

#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
typedef pair<int,int> pii;

bool cmp(pii &a, pii &b)
{
    if(a.first == b.first) return a.second < b.second;
    else return a.first < b.first;
}

bool isPossible(pii &a, pii &b, vector<string> &board)
{
    if(a.first == b.first)
    {
        for(int i=min(a.second,b.second)+1; i<max(a.second,b.second); i++)
            if(board[a.first][i] != '.') return false;
        return true;
    }
    else if(a.second == b.second)
    {
        for(int i=min(a.first,b.first)+1; i<max(a.first,b.first); i++)
            if(board[i][a.second] != '.') return false;
        return true;
    }
    else
    {
        if(a.second < b.second)
        {
            bool 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; i<b.second; i++)
                    if(board[b.first][i] != '.') {flag=false; break;}
                if(flag) return true;
            }
            
            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; i<b.first; i++)
                    if(board[i][b.second] != '.') {flag= false; break;}
                if(flag) return true;
                else return false;
            }
            else return false;
        }
        else
        {
            bool 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=b.second+1; i<=a.second; i++)
                    if(board[b.first][i] != '.') {flag=false; break;}
                if(flag) return true;
            }
            
            flag = true;
            for(int i=b.second; i<a.second; i++)
                if(board[a.first][i] != '.') {flag = false; break;}
            
            if(flag)
            {
                for(int i=a.first; i<b.first; i++)
                    if(board[i][b.second] != '.') {flag = false; break;}
                if(flag) return true;
                else return false;
            }
            else return false;
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {
    string answer = "";
    vector<vector<pii>> dt; dt.resize(26);
    queue<char> q;
    vector<bool> ck(26,0);
    vector<char> dummy;
    
    for(int i=0; i<board.size(); i++)
    {
        for(int j=0; j<board[i].size(); j++)
        {
            if(board[i][j] == '.' || board[i][j] == '*') continue;
            
            if(!ck[board[i][j]-'A']) {dummy.push_back(board[i][j]); ck[board[i][j]-'A'] = true;}
            dt[board[i][j]-'A'].push_back({i,j});       
        }
    }
    sort(dummy.begin(), dummy.end());
    for(int i=0; i<26; i++)
        if(dt[i].size()!=0) sort(dt[i].begin(), dt[i].end(), cmp);
     
    while(1)
    {
        vector<char> tmp;
        bool change = false;
        for(int i=0; i<dummy.size(); i++)
        {
            char cur = dummy[i];

            if(isPossible(dt[cur-'A'][0], dt[cur-'A'][1], board))
            {
                change = true;
                answer.push_back(cur); 
                board[dt[cur-'A'][0].first][dt[cur-'A'][0].second] = '.';
                board[dt[cur-'A'][1].first][dt[cur-'A'][1].second] = '.';
                
                for(int j=i+1; j<dummy.size(); j++) tmp.push_back(dummy[j]);
                break;
            }
            else tmp.push_back(cur);
        }
               
        if(!change) {answer="IMPOSSIBLE"; break;}
        sort(tmp.begin(), tmp.end());
        dummy = tmp;
        if(dummy.size() == 0) break;
    }
    
    return answer;
}

문제 자체를 이해하는데 있어서 난이도는 어렵지 않았지만 내용을 구현하는데 있어 살짝 시간이 오래걸릴 수 있는 문제였던거 같다.

굳