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

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

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

 

#include <string>
#include <vector>
#include <cstring>

using namespace std;

struct pos {
    int x, y;
};

int M, N;
vector<string> m_board;
vector<vector<pos>> alpha_pos;
int dr_x[] = {0, 1, 0, -1};
int dr_y[] = {1, 0, -1, 0};

bool reachable(char c, pos from, pos to)
{
    // 4방향으로 가능한 끝까지 뻗어나가기
    for (int i = 0; i < 4; ++i)
    {
        int nx = from.x + dr_x[i];
        int ny = from.y + dr_y[i];
        while (!(nx < 0 || nx >= M || ny < 0 || ny >= N))
        {
            if (nx == to.x && ny == to.y)
            {
                return true;
            }
            if (m_board[nx][ny] != '.')
            {
                break;
            }
             
            // 위아래 -> 양옆, 양옆 -> 위아래
            // 방향이 겹치지 않게 2방향으로만 뻗어나가기
            for (int j = ((i + 1) % 2); j < 4; j += 2)
            {
                int nnx = nx + dr_x[j];
                int nny = ny + dr_y[j];

                while (!(nnx < 0 || nnx >= M || nny < 0 || nny >= N))
                {
                    if (nnx == to.x && nny == to.y)
                    {
                        return true;
                    }
                    if (m_board[nnx][nny] != '.')
                    {
                        break;
                    }

                    nnx += dr_x[j];
                    nny += dr_y[j];
                }
            }

            nx += dr_x[i];
            ny += dr_y[i];
        }
    }

    return false;
}

bool game(string &answer, int left)
{
    while (true)
    {
        bool match = false;

        // 알파벳 순으로 가장 먼저인 문자열을 출력해야한다
        for (int i = 0; i < 26; ++i)
        {
            // 맞춰야할 짝이 아직 남아있다면
            if (!alpha_pos[i].empty())
            {
                char c = i + 'A';
                pos from = alpha_pos[i][0];
                pos to = alpha_pos[i][1];

                // 두 알파벳이 1번 이하로 꺾어서 닿을 수 있다면
                if (reachable(c, from, to))
                {
                    // 답 문자열에 저장
                    answer += c;

                    // 알파벳이 있던 자리 빈칸처리, alpha_pos에 저장되어 있던 위치 비우기
                    m_board[from.x][from.y] = '.';
                    m_board[to.x][to.y] = '.';
                    alpha_pos[i].clear();
                    match = true;
                    left -= 2;
                    break;
                }
            }
        }

        if (!match)
        {
            break;
        }
    }
   
    // 모든 짝이 맞춰졌으면 true반환
    return (left == 0);
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
string solution(int m, int n, vector<string> board) {

    // 전역변수 처리
    M = m;
    N = n;
    m_board = board;
    alpha_pos = vector<vector<pos>>(26);

    // 각 알파벳의 위치 2개 찾아 alpha_pos벡터에 저장
    int left = 0;
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (isalpha(board[i][j]))
            {
                // 총 알파벳 개수
                ++left;
                alpha_pos[board[i][j] - 'A'].push_back({ i, j });
            }
        }
    }

    // 짝을 모두 맞추는게 가능하면 순서 출력
    string answer = "";
    if (game(answer, left))
    {
        return answer;
    }

    // 불가능할 때
    return "IMPOSSIBLE";
}

 

 

다음의 두 조건을 해결하는 것이 이 문제의 핵심이다. 

1.
경로는 두 개 이하의 수평/수직 선분으로 구성되어 있고, 이들은 모두 연결되어 있다.
(즉, 경로를 한 번 이하로 꺾을 수 있다)
경로 상에는 다른 타일 또는 장애물이 없어야 한다.

2.
해가 여러 가지인 경우, 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

 

 

1. 경로를 한 번 이하로 꺾을 수 있다

1번 조건을 보고 기계적으로 bfs틀을 짰다가는 오히려 돌아가는 길이 될 수 있다.

1번만 꺾어 나가면 되므로, 한방향으로 쭉 뻗어나가는 액션을 2번 취하는 코드를 짜주면 된다.

코드가 좀 길어지지만 쉬운 코드이니 가독성은 괜찮다고 생각한다...?

이런 구조로...

 

 

 

2. 알파벳 순으로 가장 먼저인 문자열을 리턴한다.

처음엔 priority_queue를 활용해서 짰다. 물론 이렇게 짜도 AC는 나오지만

생각해보면 어차피 짝 하나 맞추고, 가능한 알파벳을 찾아 큐에 추가하고

또 짝 하나 맞추고, 또 가능한 알파벳을 찾아 큐에 추가하는 작업을 계속 반복해야 한다.

 

알파벳도 A~Z순으로 찾아야하는데 굳이 priority_queue가 필요치 않았다.

따라서 더이상 맞출수 있는 알파벳이 없을때까지 while반복문을 돌리고, 

그 안에 알파벳 탐색하는 반복문을 두어서 매번 A~Z순으로 탐색하게 했다.

while (true)
{
    bool match = false;

    // 알파벳 순으로 가장 먼저인 문자열을 출력해야한다
    for (int i = 0; i < 26; ++i)
    {
        // 맞춰야할 짝이 아직 남아있다면
        if (!alpha_pos[i].empty())
        {
          ...
          break;
        }
    }

    if (!match)
    {
        break;
    }
}