[프로그래머스] 리틀 프렌즈 사천성

4 분 소요

문제

출처

이해

입력

m, n (게임판 크기)
- 타입: 자연수
- 범위: [1, 100]
board (게임판 상태 정보)
- 타입: 배열
- 크기: m
- 원소
  - 타입: 문자열
  - 크기: n
  - 원소
    - 타입: 문자
    - 의미
      1. .: 빈칸
      2. *: 막힌 칸
      3. [A, Z]: 타일 종류

출력

배치된 모든 타일을 제거할 수 있다면 제거 순서대로 적은 타일의 종류, 제거할 수 없다면 “IMPOSSOBLE”

조건

같은 모양의 타일은 두 개 존재한다.
board에는 항상 타일이 존재한다.
정답이 여러 가지인 경우 알파벳 순으로 가장 빠른 문자열을 리턴한다.
다음 조건을 만족하는 경로가 있을 때 두 타일을 제거할 수 있다.
1. 경로의 양 끝이 제거하려는 두 타일일 때.
2. 경로를 한 번 이하로 꺾었을 때.
3. 경로 상에 다른 타일 또는 장애물이 없을 때.

예시

m	n	board	answer
3	3	[“DBA”, “C*A”, “CDB”]	“ABCD”
2	4	[“NRYN”, “ARYA”]	“RYAN”
4	4	[“.ZI.”, “M.**”, “MZU.”, “.IU.”]	“MUZI”
2	2	[“AB”, “BA”]	“IMPOSSIBLE”

접근

조건 3을 보면 현재 상태에서 가능한 것들을 경우의 수를 알파벳 순으로 탐색하는 종류의 문제라는 것을 알 수 있다. 그런데 탐색을 구현하는 것이 상당히 까다롭다. 구현 시에 헤매지 않으려면 다음을 이해해야 한다.

제거할 수 있는 타일이 여러 개일 때, 무엇을 먼저 지우든 지울 수 있는 총 타일 수는 변하지 않는다.
- 수가 변하려면 지울 수 없는 타일이라는 판정이 게임 진행에 따라서 뒤집힐 수 있어야 한다. 판정이 뒤집히려면 없던 장애물이 생겨나거나, 이미 삭제된 타일이 부활해야 한다. 하지만 이런 규칙은 주어지지 않았다.
임의의 두 타일의 경로는 여덟 가지 패턴으로 분류할 수 있다.
- 두 타일 중 하나를 중앙에 두고 나머지 하나의 타일의 위치를 생각해보면 쉽게 이해할 수 있다.
  - 1, 3, 6, 8에 위치하면 한 번 꺾어지는 경로를 2개 가진다.
  - 2, 4, 5, 7에 위치하면 직선 경로 1개를 가진다.

\[\begin{matrix} 1 & 1 & 2 & 3 & 3\\ 1 & 1 & 2 & 3 & 3\\ 4 & 4 & * & 5 & 5\\ 6 & 6 & 7 & 8 & 8\\ 6 & 6 & 7 & 8 & 8\\ \end{matrix}\]

위 내용을 정리하면 다음과 같은 pseudo code를 생각해볼 수 있다.

모든 타일을 제거했다면 답을 출력하고 종료한다.
현재 board 상태에서 지울 수 있는 모든 타일 쌍을 찾는다.
지울 수 있는 타일이 없으면 IMPOSSIBLE을 출력하고 종료한다.
지울 수 있는 타일이 있다면 알파벳 순으로 봤을 때 가장 빠른 타일을 지운다.
1로 돌아간다.

중요한 부분은 지울 수 있는 모든 타일 쌍을 찾는 방법이다. DFS나 BFS로 탐색할 수도 있지만 조건 4에 의하여 두 타일을 잇는 경로가 제한되므로 해당 경로 중 하나가 비어있는지만 확인하면 더 빠르게 문제를 해결할 수 있다.

간단한 트릭아닌 트릭으로 타일 경로 패턴 여덟 가지를 절반으로 줄일 수 있다. 타일의 쌍을 찾을 때 좌측에서 우측으로, 위에서 아래로 찾는 것이다. 너무 당연한 방법이지만, 이렇게 하면 먼저 찾아진 타일을 중심으로 볼 때 두 번째로 찾아진 타일은 5, 6, 7, 8에만 존재할 수 있다.

\[\begin{matrix} X & X & X & X & X\\ X & X & X & X & X\\ X & X & * & 5 & 5\\ 6 & 6 & 7 & 8 & 8\\ 6 & 6 & 7 & 8 & 8\\ \end{matrix}\]

이런 내용을 아주 꼼꼼하게 구현하면 된다.

그밖에도 재미있는 풀이가 있었는데, 타일 쌍을 잇는 경로에 존재하는 다른 타일에 포커스를 두는 풀이이다. 경로에 존재하는 다른 타일이 모두 제거되어야 현재 타일 쌍도 제거할 수 있으므로 이 의존 관계를 유향 그래프로 나타내서 위상정렬로 답을 구할 수 있다고 한다. 물론 경로 상에 어떤 타일이 존재하는지 알아내야 하기 때문에 마찬가지로 까다로운 구현은 피할 수 없다.

구현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct pos {
    int y, x;
};

int n_pair;
vector<vector<pos>> pairs;
vector<string> board;
vector<bool> erased;
string answer;

bool empty_line(int dir, int a, int b1, int b2) {
    /*
        a행 (또는 열)을 기준으로 [b1, b2] 영역이 empty이면 return true

        dir: 0 가로 방향 탐색, 1 세로 방향 탐색
        a: 탐색할 행 또는 열
        b1: 구간 시작점
        b2: 구간 끝점
    */
    bool empty = true;
    for (int i = b1; i <= b2 && empty; i++) {
        char target = dir ? board[i][a] : board[a][i];
        switch (target) {
            case '*': empty = false; break; // 장애물
            case '.': break; // 빈칸은 통과 가능
            default: empty = erased[target-'A']; // 삭제된 경우 통과 가능
        }
    }
    return empty;
}

bool reachable(const vector<pos>& v) {
    /*
        조건을 만족하면서 주어진 두 타일을 연결하는 경로가 존재하면 return true
    */
    const pos &a = v[0], &b = v[1];
    bool check = true;
    if (a.y < b.y && a.x < b.x) // 8번 위치인 경우
        check = (empty_line(0, a.y, a.x + 1, b.x) && empty_line(1, b.x, a.y, b.y - 1)) 
             || (empty_line(1, a.x, a.y + 1, b.y) && empty_line(0, b.y, a.x, b.x - 1));
    else if (a.y < b.y && a.x > b.x) // 6번
        check = (empty_line(0, a.y, b.x, a.x - 1) && empty_line(1, b.x, a.y, b.y - 1))
             || (empty_line(1, a.x, a.y + 1, b.y) && empty_line(0, b.y, b.x + 1, a.x));
    else if (a.y == b.y) // 5번
        check = empty_line(0, a.y, a.x + 1, b.x - 1);
    else // 7번
        check = empty_line(1, a.x, a.y + 1, b.y - 1);
    return check;
}

bool run() {
    /*
        사천성을 시뮬레이션 하여 해를 찾을 수 있을 때 return true 하는 함수
    */
    while (true) {
        // 모든 타일을 제거한 경우 return true
        if (answer.size() == n_pair)
            return true;
        // 타일을 알파벳 순으로 확인함
        for (int type = 0; type < 26; type++) {
            // 제거 가능한 최초의 타일을 제거하고. 알파벳 처음부터 다시 확인.
            if (pairs[type].size() && !erased[type] && reachable(pairs[type])) {
                erased[type] = true;
                answer.push_back(type + 'A');
                break;
            }
            // 타일이 남았는데 제거할 수 있는 타일이 없으면 return false
            if (type == 25)
                return false;
        }
    }
}

string solution(int m, int n, vector<string> tmp) {
    // 프로그래머스에서 전역 변수를 사용할 때에는 항상 초기화가 필요하다. (clear)
    n_pair = 0; answer = ""; board = tmp;
    pairs.clear(); pairs.resize(26, vector<pos>());
    erased.clear(); erased.resize(26, false);
    
    // 보드에 존재하는 타일의 쌍을, 종류 별로 기록한다.
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if ('A' <= board[i][j] && board[i][j] <= 'Z')
                pairs[board[i][j]-'A'].push_back({i, j});
    
    // 타일 종류의 수를 구한다.
    n_pair = count_if(pairs.begin(), pairs.end(), [](auto& pair) { 
        return pair.size() > 0; 
    });
    
    return run() ? answer : "IMPOSSIBLE";
}

Kuropow

[프로그래머스] 리틀 프렌즈 사천성

문제

이해

입력

출력

조건

예시

접근

구현

댓글남기기

참고

[백준] 마지막 팩토리얼 수2 - Python

[백준] 하이퍼 토마토

[프로그래머스] 디스크 컨트롤러

[프로그래머스] 오랜 기간 보호한 동물(2)