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

문제

Programmers 2017 카카오코드 본선 : 리틀 프렌즈 사천성

코딩테스트 연습 - 리틀 프렌즈 사천성

접근

먼저 A부터 Z까지의 타일의 좌표를 알파벳별로 배열에 저장해준다. 해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 반환해야 하므로 알파벳 순으로 for문을 돌면서 가장 먼저 제거할 수 있는 타일을 제거해준다. 이때 제거한 타일에 의해 이전에는 제거하지 못했던 타일의 제거가 가능해질 수 있기 때문에 다시 알파벳의 A부터 for문을 초기화해서 제거 가능한 타일을 검사해준다. 그렇다면 자연스럽게 알파벳 순으로 가장 먼저인 문자열을 반환할 수 있을 것이다.

여기서 타일을 제거할 수 있는지 검사하는 방법은 간단하다. 경로는 두 개 이하의 수직/수평선을 통해 만들 수 있기 때문에 타일 A₁이 타일 A₂까지 갈 수 있는 경로는 아래 사진에서 볼 수 있는 두 가지 이다.

따라서 x축 이동과 y축 이동을 하는 함수를 따로 만들어서 무사히 이동을 할 수 있으면 true를 return 해주도록 만들었다. 두 경로 중 하나의 경로라도 완전히 이동할 수 있다면 이 타일은 제거할 수 있는 타일이므로 지워주면 된다. 이렇게 제거가 불가능한 타일이 나올 때까지 혹은 모든 타일을 제거할 때까지 반복문을 돌아주고 결과를 반환하면 된다.

 

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

bool go_x(int x1, int y1, int x2, int y2, vector<string> board) {
    char go = '+';
    if (x1 == x2)
        return true;
    else if (x1 > x2)
        go = '-';

    while (1) {
        if (go == '-')
            x1--;
        else
            x1++;
        if (board[x1][y1] != '.') {
            if (board[x1][y1] == board[x2][y2])
                return true;
            else
                return false;
        } else if (board[x1][y1] == '.' && x1 == x2)
            return true;
    }
}

bool go_y(int x1, int y1, int x2, int y2, vector<string> board) {
    char go = '+';
    if (y1 == y2)
        return true;
    else if (y1 > y2)
        go = '-';

    while (1) {
        if (go == '-')
            y1--;
        else
            y1++;
        if (board[x1][y1] != '.') {
            if (board[x1][y1] == board[x2][y2])
                return true;
            else
                return false;
        } else if (board[x1][y1] == '.' && y1 == y2)
            return true;
    }
}
string solution(int m, int n, vector<string> board) {
    string answer = "";
    vector<pair<int, int>> save[30];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
                save[board[i][j] - 'A'].push_back(make_pair(i, j));
        }
    }
    while (1) {
        int chk = 0;
        for (int i = 0; i < 26; i++) {
            if (save[i].size() == 0)
                continue;
            chk = -1;
            if (go_x(save[i][0].first, save[i][0].second, save[i][1].first, save[i][1].second, board) && go_y(save[i][1].first, save[i][0].second, save[i][1].first, save[i][1].second, board)) {
                chk = 1;
                answer.push_back(board[save[i][0].first][save[i][0].second]);
                board[save[i][0].first][save[i][0].second] = '.';
                board[save[i][1].first][save[i][1].second] = '.';
                save[i].clear();
                break;
            }
            if (go_x(save[i][1].first, save[i][1].second, save[i][0].first, save[i][0].second, board) && go_y(save[i][0].first, save[i][1].second, save[i][0].first, save[i][0].second, board)) {
                chk = 1;
                answer.push_back(board[save[i][0].first][save[i][0].second]);
                board[save[i][0].first][save[i][0].second] = '.';
                board[save[i][1].first][save[i][1].second] = '.';
                save[i].clear();
                break;
            }
        }
        if (chk == 0)
            return answer;
        else if (chk == -1)
            return "IMPOSSIBLE";
    }
    return answer;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study