[C++] 2017 카카오코드 본선 리틀 프렌즈 사천성

문제 설명

---

리틀 프렌즈 사천성

언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만 준비해서 냄비에 넣고 휘젓기만 하면 순식간에 최고의 요리로 만들어주는 신비의 아이템. 어느 날 매직 스푼을 호시탐탐 노리는 악당들이 보물을 훔쳐간다. 매직 스푼을 되찾고 다시 마을에 평화를 가져오기 위해 프렌즈의 대모험이 시작되는데...

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

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

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

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

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

입력 형식

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

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

출력 형식

해가 존재하는 경우 타일을 제거하는 순서대로 한 글자씩 이루어진 문자열을, 그렇지 않은 경우 IMPOSSIBLE을 리턴한다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

예제 입출력

mnboardanswer

3	3	["DBA", "C*A", "CDB"]	"ABCD"
2	4	["NRYN", "ARYA"]	"RYAN"
4	4	[".ZI.", "M.**", "MZU.", ".IU."]	"MUZI"
2	2	["AB", "BA"]	"IMPOSSIBLE"

예제에 대한 설명

첫 번째 테스트 케이스에서 처음으로 제거 가능한 타일은 A와 C이다. 그리고 모든 가능한 경우를 나열하면 ABCD, ACBD, ACDB, CABD, CADB, CDAB이다. 이 중 알파벳 순으로 가장 먼저인 ABCD가 정답이다.

네 번째 테스트 케이스는 초기 상태에서 제거할 수 있는 타일이 없으므로 타일을 모두 제거하는 것이 불가능하다. 따라서 정답은 IMPOSSIBLE이다.

 

 

 

 

접근 방법

---

문제 풀이를 떠올리는 것은 어렵지 않았습니다. 하지만 치명적 실수 때문에 시간을 꽤 오래 잡았고 큰 깨달음을 얻게 해준 문제였습니다.

 

(!!!혹시 테스트 케이스는 다 맞는데 틀리는 분들을 위해 일단 제 실수에 대해 설명드리겠습니다.)

저는 문제를 보자마자 짝을 찾는 방법에 대해 BFS를 떠올렸습니다.

BFS를 사용할 때 visited로 방문체크를 하였는데 이게 가장 치명적인 실수였습니다.

 

만약 아래와 같이 입력이 주어졌을 때

 

BFS탐색 순서에 따라 아래와 같은 경로가 가능함에도 불구하고

 

좌측 사진과 같은 순서로 먼저 탐색이 된다면 우측 사진의 경로로 탐색이 불가능 하다는 점이었습니다.

 

왜냐하면 1,2 지점에 visited[1][2] = true가 되기 때문에 1,2지점으로 갈 수 없기 때문입니다.

 

 즉, 탐색을 할 경우 BFS의 경우 약간의 변형을 통해 visited를 사용하지 않거나, DFS(모든 지점 방문이 목적)의 경우 backTracking(모든 경로 탐색이 목적)을 사용한다면 이러한 문제점을 극복할 수 있습니다.

 

 

문제풀이는 아래와 같습니다.

1. (A~Z) 짝의 좌표를 저장 (동시에 제거 해야할 짝의 수를 증가->나중에 모든 짝이 제거되었는지 확인하기 위한 목적)

2. A~Z까지 제거 가능한 짝이 있는지 검사

3. 2에서 제거 가능한 짝이 있다면 제거 후, A부터 다시 검사

(A부터 검사하는 이유는 가능한 경우에 대해 사전 순 정렬 목적)

4. 제거할 수 있는 짝이 없다면 완전히 제거가 되었는지 검사

 

자세한 내용은 소스코드에 주석 처리 하였습니다.

 

 

소스 코드

---

#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef struct qinfo{
//행, 열, 방향, 꺾은 횟수
    int x,y,dir,cnt;
};
typedef struct ainfo{
    int x,y;
};

int pairCnt = 0;
int N = 0,M = 0;

bool inRange(int x, int y){
    return (0 <= x && x < M && 0 <= y && y < N);
}

bool BFS(int start_x, int start_y, int end_x, int end_y, vector<string> &boards){
    
    pair<int, int> nextdir[4] = {{1,0},{0,1},{-1,0},{0,-1}};
    
    queue<qinfo> q;
    
    //어떤 방향으로 출발해도 상관 없다는 표시로 dir = -1;
    q.push({start_x, start_y, -1, 0});
    
    while(!q.empty()){
        
        int now_x = q.front().x; int now_y = q.front().y;
        int cnt = q.front().cnt; int dir = q.front().dir;
        q.pop();
        
        for(int i=0;i<4;i++){
            
            //dir이 -1이 아닐 때 역 방향이라면 continue
            if(dir != -1 && abs(dir - i) == 2)
                continue;
            
            int next_x = now_x + nextdir[i].first;
            int next_y = now_y + nextdir[i].second;
            int next_cnt = (dir == i || dir == -1) ? cnt:cnt+1; //방향이 다르다면 꺾어야만 함
            
            if(inRange(next_x, next_y)){
                //어디로 가던지 꺾은 횟수가 1번 이하여야 함
                if(next_cnt <= 1){
                    if(boards[next_x][next_y] == '*'){
                        continue;
                    }
                    else if(boards[next_x][next_y] == '.'){
                        q.push({next_x, next_y, i, next_cnt});
                    }
                    else {
                        //제거 할 수 있는 패를 찾았다면
                        if(next_x == end_x && next_y == end_y)
                            return true;
                    }    
                }
            }
        }
    }
    return false;
}

string solve(vector<vector<ainfo>> &arr, vector<string> &boards){
    
    string ans = "";
    bool flag = true;
    
    while(flag){
        
        flag = false;
        
        //2번 과정, A~Z까지 검사
        for(int i=0;i<arr.size();i++){
            //해결 해야할 요소가 있다면
            if(arr[i].size() > 1){
            	//BFS를 통해 제거 가능한 짝이 있는지 검사
                if(BFS(arr[i][0].x, arr[i][0].y, arr[i][1].x, arr[i][1].y, boards)){
                	//3번 과정, 제거한 부분을 빈 공간으로 변경
                    boards[arr[i][0].x][arr[i][0].y] = boards[arr[i][1].x][arr[i][1].y] = '.'; //빈칸으로 만듬
                    arr[i].clear(); //배열 정보 삭제
                    pairCnt -= 2; //제거 해야할 짝의 수 감소
                    ans += char(i + int('A')); 
                    flag = true;
                    break;
                }    
            }
        }   
    }
    
    //4번 과정
    if(pairCnt == 0) //모든 짝을 제거한 경우
        return ans;
    else //더 이상 해결을 못하는 경우
        return "IMPOSSIBLE";
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {
    
    string answer = "";
    vector<vector<ainfo>> arr(26, vector<ainfo>());
    
    //전역 변수 초기화
    pairCnt = 0;
    M=m; N=n;
    
    //1번 과정, 모든 짝의 위치를 저장
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if('A' <= board[i][j] && board[i][j] <= 'Z'){
            	//alphabet을 int로 변환 후 위치 저장
                arr[int(board[i][j]) - int('A')].push_back({i,j});
                pairCnt++; //제거 해야 할 짝의 수 증가
            }
        }
    }
                
    return answer = solve(arr,board);
}