[C++로 풀이] 리틀 프렌즈 사천성 (BFS, 다익스트라)⭐⭐⭐

Date: 2021.03.30 Updated: 2021.03.30

카테고리: Programmers

📌 리틀 프렌즈 사천성

난이도 ⭐⭐⭐

🚀 문제

🚀 내 풀이

최대한 제거 가능한 선에서 알파벳 순으로 가장 먼저인 것을 제거해야 한다. 따라서 알파벳 순서가 가장 빠른 것 ⭐한 개⭐를 제거하고, 또 제거 가능한 것들을 검사하여 그 중 알파벳 순서가 가장 빠른 것 한개를 제거하고.. 또 제거할 수 있는 것 검사하고.. 이 행위를 더 이상 제거 가능한 알파벳이 없을 때까지 반복하면 된다!

제거 가능 기준 : 같은 두 알파벳이 1 번 이하로 경로를 꺾을 수 있는 것만 제거할 수 있다.
- 0 번 꺾는 것 👉 같은 행 (ㅡ 모양), 같은 열 (│ 모양)
- 1 번 꺾는 것 👉 ┌ , ┐ , └ , ┘ 이런 모양의 경로여야 한다.

🔥 첫 번째 풀이 : 일일이 경로를 찾아 검사 ⭕

추후 제거하기로 결정된 알파벳들을 v 벡터에 넣을 것이고 v_index로 이 v 벡터에서 이번에 제거할 순서인 하나의 알파벳를 가리키게 할 것이다.
remove set 에 현재의 board에서 제거 가능한 알파벳들을 후보로 담을 것이다.
- 그리고 모두 담고나면
  - v에 추가하되 v_index의 뒤에 있는(이번에 제거된 알파벳보다 뒷 순서에 오는게 당연하므로) v내의 알파벳들 중 정렬 순서에 맞는 알맞는 자리에 추가하면 된다.
  - 이미 v에 있다면 추가하지 않는다.

위와 같은 방식으로 코드를 짰다. 하 근데 1번 꺾는 경로에서 짝꿍 알파벳을 찾는 것을 구현하는게 좀 힘들었다. 머리가 안 돌아가요..😂 근데 이 과정을 BFS 로 푸신 분이 계셔서 나도 BFS 로 풀어보았다.

🔥 첫 번째 풀이 : 0 번 (ㅡ, │), 1 번 (┌ , ┐ , └ , ┘) 꺾어서 갈 수 있는 모든 경로에 짝꿍 알파벳이 있는지 일일이 검사함 (~~힘들어따..~~)
- 여담으로 만약 문제가 1 번 이하로 꺾는 것 이 아닌, n이 2 이상일 때, n 번 이하로 꺾게 하는 문제였다면 이 풀이론 풀지 못했을 것이다. 문제가 1 번 이하로 꺾는 것이라고 하여 경우의 수가 ┌ , ┐ , └ , ┘ 이렇게 4 가지 뿐이니 가능했지만, 원래 프렌즈 사천성 게임처럼 2번까지 꺾는걸 허용했다면 이 노가다식 풀이로는 구현하기가 정말 어려웠을 것이다. 따라서 2 번 이상으로 꺾는 것도 가능한 문제였다면 군말 없이 BFS 혹은 다익스트라를 사용하여 꺾는 횟수가 2번 이하인 경로들을 구했어야 했을 것이다.
🔥 두 번째 풀이 : BFS 로 짝꿍 알파벳 찾기

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

using namespace std;

struct Pos {
    int r;
    int c;
};

string solution(int m, int n, vector<string> board) {
    string answer = "";
    // 인덱스는 알파벳에 대응. 알파벳 별로 위치 저장. 
    // pos_record[i][0], pos_record[i][1]  i 번쨰 알파벳인 두 글자의 위치
    vector<vector<Pos>> pos_record(26); 

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == '*' || board[i][j] == '.')
                continue;
            pos_record[board[i][j] - 'A'].push_back({ i, j });
        }
    }  

    vector<char> v; // "최종 제거 순서"  
    int v_index = -1; // v 의 인덱스. 이 인덱스가 가리키는 v 의 알파벳이 이번에 제거할 알파벳이다. 이 인덱스가 가리키는 v내의 알파벳 뒤에 있는 것들에서 알파벳 정렬 순서에 맞게 새로운 알파벳이 추가 될 것이다. 
    while (true) {
        set<char> remove; // "제거 후보." while문의 반복마다 현재의 board 에서 제거 가능한 알파벳 정렬된 순서대로 차례대로 여기에 추가할 것.
        for (int k = 0; k < 26; ++k) {
            if (pos_record[k].empty()) continue; // board에 없는 알파벳이라면 넘어감
            
            bool OK = true;
            
            // 경로 0 번 꺾기 (같은 행 사이에 장애물 있는지 검사)
            if (pos_record[k][0].r == pos_record[k][1].r) { // 짝꿍인 두 알파벳끼리 같은 행이라면 두 열의 사이에 장애물(* 혹은 다른 알파벳)이 있는지 검사한다.
                // ㅡ 모양의 경로
                OK = true;
                int i = pos_record[k][0].r;
                for (int j = pos_record[k][0].c + 1; j < pos_record[k][1].c; ++j) {
                    if (board[i][j] == '*') { OK = false; break; }
                    if (board[i][j] >= 'A' && board[i][j] <= 'Z') { OK = false; break; }
                }
                if (OK) { // 장애물이 없다면 remove 에 추가
                    remove.insert(k + 'A');
                    continue;
                }
            }

            // 경로 0 번 꺾기 (같은 열 사이에 장애물 있는지 검사)
            if (pos_record[k][0].c == pos_record[k][1].c) { // 짝꿍인 두 알파벳끼리 같은 열이라면 두 행의 사이에 장애물(* 혹은 다른 알파벳)이 있는지 검사한다.
                // │ 모양의 경로
                OK = true;
                int j = pos_record[k][0].c;
                for (int i = pos_record[k][0].r + 1; i < pos_record[k][1].r; ++i) {
                    if (board[i][j] == '*') { OK = false; break; }
                    if (board[i][j] >= 'A' && board[i][j] <= 'Z') { OK = false; break; }
                }
                if (OK) { // 장애물이 없다면 remove 에 추가
                    remove.insert(k + 'A');
                    continue;
                }
            }

            // 경로 1 번 꺾기 
            if (pos_record[k][0].c < pos_record[k][1].c) {  // ㄴ, ㄱ. 
                // ㄴ 모양의 경로 (ㄴ 의 왼쪽 위가 pos_record[k][0], 오른쪽 아래가 pos_record[k][1])
                OK = true;
                // (point_r, point_c) 는 꺾이는 위치
                int point_r = pos_record[k][1].r;
                int point_c = pos_record[k][0].c;
                
                // ㄴ의 │ 
                for (int i = pos_record[k][0].r + 1; i <= point_r; ++i) {
                    if (board[i][point_c] == '*') { OK = false; break; }
                    if (board[i][point_c] >= 'A' && board[i][point_c] <= 'Z') { OK = false; break; }
                }
                // ㄴ의 ㅡ
                for (int j = point_c; j < pos_record[k][1].c; ++j) {
                    if (board[point_r][j] == '*') { OK = false; break; }
                    if (board[point_r][j] >= 'A' && board[point_r][j] <= 'Z') { OK = false; break; }
                }
                if (OK) {
                    remove.insert(k + 'A');
                    continue;
                }

                // ㄱ 모양의 경로 (ㄱ 의 왼쪽 위가 pos_record[k][0], 오른쪽 아래가 pos_record[k][1])
                OK = true;
                // (point_r, point_c) 는 꺾이는 위치
                point_r = pos_record[k][0].r;
                point_c = pos_record[k][1].c;

                // ㄱ 의 ㅡ
                for (int j = pos_record[k][0].c + 1; j <= point_c; ++j) {
                    if (board[point_r][j] == '*') { OK = false; break; }
                    if (board[point_r][j] >= 'A' && board[point_r][j] <= 'Z') { OK = false; break; }
                }
                // ㄱ 의 │
                for (int i = point_r; i < pos_record[k][1].r; ++i) {
                    if (board[i][point_c] == '*') { OK = false; break; }
                    if (board[i][point_c] >= 'A' && board[i][point_c] <= 'Z') { OK = false; break; }
                }
                if (OK) {
                    remove.insert(k + 'A');
                    continue;
                }
            }
            if (pos_record[k][0].c > pos_record[k][1].c) { // ┌ , ┘
                // ┘ 모양의 경로 ( ┘ 의 오른쪽 위가 pos_record[k][0], 왼쪽 아래가 pos_record[k][1])
                OK = true;
                // (point_r, point_c) 는 꺾이는 위치
                int point_r = pos_record[k][1].r;
                int point_c = pos_record[k][0].c;

                // ┘ 의 │
                for (int i = pos_record[k][0].r + 1; i <= point_r; ++i) {
                    if (board[i][point_c] == '*') { OK = false; break; }
                    if (board[i][point_c] >= 'A' && board[i][point_c] <= 'Z') { OK = false; break; }
                }
                // ┘ 의 ㅡ
                for (int j = pos_record[k][1].c + 1; j <= point_c; ++j) {
                    if (board[point_r][j] == '*') { OK = false; break; }
                    if (board[point_r][j] >= 'A' && board[point_r][j] <= 'Z') { OK = false; break; }
                }
                if (OK) {
                    remove.insert(k + 'A');
                    continue;
                }

                // ┌ 모양의 경로 ( ┌ 의 오른쪽 위가 pos_record[k][0], 왼쪽 아래가 pos_record[k][1])
                OK = true;
                // (point_r, point_c) 는 꺾이는 위치
                point_r = pos_record[k][0].r;
                point_c = pos_record[k][1].c;

                // ┌ 의 ㅡ
                for (int j = point_c; j < pos_record[k][0].c; ++j) {
                    if (board[point_r][j] == '*') { OK = false; break; }
                    if (board[point_r][j] >= 'A' && board[point_r][j] <= 'Z') { OK = false; break; }
                }
                // ┌ 의 │
                for (int i = point_r; i < pos_record[k][1].r; ++i) {
                    if (board[i][point_c] == '*') { OK = false; break; }
                    if (board[i][point_c] >= 'A' && board[i][point_c] <= 'Z') { OK = false; break; }
                }
                if (OK) {
                    remove.insert(k + 'A');
                    continue;
                }
            }
        }

        if (remove.empty()) break; // 현재 board 에서 하나도 제거할 수 있는게 없었다면 while문 종료

        // 현재 board 에서 제거 가능한 알파벳들을 v 에 "알파벳 순서"에 맞춰 추가 (단, v_index 가 가리키는 알파벳 뒤에 추가. v_index는 이번 턴에 제거한 알파벳의 포인터이기 때문)
        for (auto& ele : remove) {
            int i = 0;
            // 이미 v 에 있다면 추가하지 않음
            if (find(v.begin(), v.end(), ele) != v.end())
                continue;

            // 추가되야할 위치 찾기 (v_index 뒤, 정렬된 순서 유지)
            for (i = v_index + 1; i < v.size(); ++i) 
                if (ele < v[i])
                    break;
            
            if (v.empty()) v.push_back(ele); // v 가 비어있는 처음 턴에선 그냥 바로 추가
            else v.insert(v.begin() + i, ele); // 위에서 찾은 위치 i 자리에 추가
        }

        v_index++;

        // v[v_index] 알파벳 2 개 제거하기
        char next_remove_char = v[v_index];
        Pos pos_next_remove_char1{ pos_record[next_remove_char - 'A'][0].r, pos_record[next_remove_char - 'A'][0].c }; // 위치
        Pos pos_next_remove_char2{ pos_record[next_remove_char - 'A'][1].r, pos_record[next_remove_char - 'A'][1].c }; // 위치
        board[pos_next_remove_char1.r][pos_next_remove_char1.c] = '.'; // 제거
        board[pos_next_remove_char2.r][pos_next_remove_char2.c] = '.'; // 제거
        pos_record[next_remove_char - 'A'].clear(); // pos_record 에서도 두 위치 담은 벡터 지우기 
    }

    // 더 이상 제거할게 없어서 while문 종료 후 빠져나왔는데 알파벳이 아직 남아있다면 제거 불가능한 알파벳이 있다는 뜻이므로 "IMPOSSIBLE" 리턴
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
                return "IMPOSSIBLE";

    // 알파벳이 모두 제거되었다면 v 에 차례로 담긴 알파벳이 답이 된다.
    for (int i = 0; i < v.size(); ++i)
        answer += v[i];

    return answer;
}

그나저나 이 문제.. 8 점이나 준다! 레벨 3 문제들 점수 1,2 점 주는게 대부분이였는데 ㅠ ㅠ 아무튼 그래서 채점 후 특히 기분 좋았던 문제였다.💛

🔥 두 번째 풀이 : BFS ⭕

풀이는 https://wlshddlek.tistory.com/63?category=882537 진홍이님 블로그를 참고하여 작성했다. 나는 일일이 6 개의 경로를 검사하였는데 이 분 풀이를 보고 아 맞다 BFS 로 풀 수 있겠구나 싶어서 무릎을 탁.. BFS 문제를 다양하게 풀어보고 싶다.

BFS 로 1 번 이하로 꺾어 갈 수 있는 곳들만 탐색한다. 두 알파벳 위치 중 하나만 map에 저장한 후 이 위치를 시작점으로 나머지 알파벳에 1 번 이하로 꺾어서 도착할 수 있는지 BFS 로 탐색한다. 불가능하다면 찾지 못한채로 빠져나오게 한다. 그건 현재 board에서 제거할 수 없는 알파벳인 것이다.

마찬가지로 현재 board 에서 제거 가능한 알파벳들 중 알파벳 순서가 가장 빠른 알파벳 종류를 딱 하나만 제거한다. map 은 자동 정렬이 되기 때문에 Key 를 알파벳으로 하여 나머지 하나의 위치를 저장한 map의 요소들을 차례대로 넣으면 알파벳 순서대로 넘겨주는 것과 같으며, map의 Value 인 위치를 시작점으로 나머지 짝꿍 알파벳을 1 번 이하로 꺾어 가는 것이 가능한지를 BFS 로 탐색하여 구하면 된다.

BFS 로 ⭐여태까지 꺾은 횟수⭐ 고려하여 탐색하기

모든 위치마다 시작점으로부터 현재까지 꺾어진 횟수를 기억해야 한다.
- 꺾는 것은 그때 그때 방문하는 위치가 향하는 방향에 따라 다르기 때문에 가중치 없는 그래프에서의 최단’거리’와는 다르게 BFS 방식으로 너비 우선 탐색을 하더라도 더 적은 횟수로 꺾을 수 있는 경로를 찾아낼 가능성이 있다.
- 따라서 동일한 위치더라도 더 적게 꺾어서 올 수 있다면 다시 재방문(큐에 또 삽입) 할 수 있어야 한다. 그 위치로부터 뻗어나가는 모든 위치들도 다 새롭게 꺾은 횟수로 업데이트 되야하니까!
- 그래서 구조체에도 꺾은 횟수를 담고 우선순위큐를 써서 다익스트라로 풀 수도 있다.
큐에 삽입되는 기준 👉 상,하,좌,우 갈 수 있는 곳들 중에서 꺾은 횟수가 1 이하인 위치만 삽입 가능

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

using namespace std;

struct Pos {
    int r; // 행
    int c; // 열
    int dir; // ⭐방향⭐ (현재 향하고 있는 방향을 알아서 다음 위치를 큐에 삽입할 때 꺾어야할지를 알 수 있다.) 
};

#define INF 987654321
#define alpha first 
#define pos second 

vector<string> Board;
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };

int M, N;
map<char, Pos> pos_record; // key : 알파벳  value : 위치 (두 알파벳 중 하나만. 그리고 나머지는 BFS 로 찾는다.)

Pos BFS(Pos start, char start_alpha) { // start 출발 위치, start_alpha 출발지 알파벳
    queue<Pos> q;
    vector<vector<int>> turn_and_check(M, vector<int>(N, INF)); // 꺾은 횟수 저장

    // 출발 지점 예약
    start.dir = -1;
    q.push(start);
    turn_and_check[start.r][start.c] = 0;

    bool not_first = false; // 출발지의 알파벳과 동일한 위치에서 종료할건데 바로 출발지의 알파벳과 동일하다고 판정되어 종료되면 안되기 때문에 사용할 플래그
    while (!q.empty()) {
        // 방문
        Pos now = q.front();
        q.pop();

        // 짝꿍을 찾았다면! (출발지가 아니고!)
        if (not_first && Board[now.r][now.c] == start_alpha)
            return { now.r, now.c }; // 제거 가능하다는 뜻이다. 이 짝꿍 알파벳 위치를 리턴하고 종료.
        not_first = true; // 출발지 방문시에만 false 상태고 나머지 위치 방문시엔 모두 true 인 상태

        for (int i = 0; i < 4; ++i) {
            int nextR = now.r + dr[i];
            int nextC = now.c + dc[i];
            int nextDir = i;
            int next_turn_count = turn_and_check[now.r][now.c]; // 현재 방문 위치까지 꺾은 횟수가 초기값
            if (now.dir != -1 && now.dir != nextDir) // 출발지가 아니고(출발지의 방향은 -1로 하였다. 출발지에서 예약되는 위치들은 꺾였다고 판단되지 않기 위해) 방향이 일치하지 않으면 꺾어야 한다. 꺾는 횟수를 1 증가시켜야 한다.
                next_turn_count++;

            // 다음 방문 후보 검사
            if (nextR < 0 || nextR >= M || nextC < 0 || nextC >= N) // 1. 범위 내에 있어야 함
                continue;
            if (next_turn_count >= 2) // ⭐2. 꺾은 횟수가 2 이상이 되면 그 위치는 탐색하지 않는다.⭐
                continue;
            if (Board[nextR][nextC] != '.' && Board[nextR][nextC] != start_alpha) // 3. 장애물이 아니어야 함
                continue;
            if (turn_and_check[nextR][nextC] >= next_turn_count) { // 4. 기존에 찾은 꺾은 횟수 그 이하로 꺾을 수 있다면 더 적은 횟수로 꺾을 수 있는 가능성이 있는 탐색 경로가 되므로 또 삽입
                q.push({ nextR, nextC, nextDir });
                turn_and_check[nextR][nextC] = next_turn_count; // 위치별 현재까지 꺾은 횟수 업데이트
            }
        }
    }
    return { -1, -1 }; // while문을 빠져나왔다면 짝꿍알파벳을 찾지 못한 것이다. 즉, 제거 불가능! 제거 불가능시에는 {-1, -1}를 리턴하기로 했다.
}

string solution(int m, int n, vector<string> board) {
    string answer = "";
    M = m;
    N = n;
    Board = board;

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
                pos_record[board[i][j]] = { i, j }; // 두 위치 중 하나의 위치만 담음. 

    while (true) {
        bool canRemove = false; // 이번 board에서 제거 할 수 있는 알파벳이 있었다는 것을 표시
        // 현재 board 상태에서 처음으로 제거 가능한 알파벳을 발견하자마자 break (알파벳은 딱 한 종류만 제거함)
        // pos_record 는 map 이기 때문에 letter 는 자동으로 알파벳 순서대로 
        for (auto& letter : pos_record) {
            char start_alpha = letter.alpha;
            Pos start = letter.pos;
            Pos dest = BFS(start, start_alpha); // 짝꿍 알파벳 위치 (못찾았다면, 즉 제거 불가능하다면 {-1, -1} 리턴받음)
            if (dest.r != -1 && dest.c != -1){ // 제거 가능하다면
                canRemove = true; 
                Board[start.r][start.c] = '.'; // 제거
                Board[dest.r][dest.c] = '.'; // 제거
                answer += start_alpha; // answer 에 반영
                pos_record.erase(start_alpha); // map 에서 지우기
                break;
            }
        }

        if (canRemove) // 지울 수 있는 알파벳이 있었다면 다시 현재의 board 에서 또 제거 가능한 알파벳 중 가장 앞선 순서의 알파벳 제거하러 고고 
            continue;

        if (pos_record.empty()) // map 이 비었다는건 알파벳을 전부 제거했다는 의미
            return answer;
        else // canRemove 는 false 인데 (즉 더 이상 board에서 지울 수 있는게 없음) map 은 비지 않았다면 제거 불가능한 알파벳들이 있다는 의미
            return "IMPOSSIBLE";
    }
}

🔥 세 번째 풀이 : 다익스트라 ⭕

우선순위 큐 사용 (힙정렬 기준은 꺾은 횟수가 가장 적은게 루트에 오도록)
구조체에 꺾은 횟수 저장
힙정렬과 수많은 재방문 때문인지 BFS 보다 시간은 두 배 정도 더 걸렸다.
- 방문 체크를 따로 두고 예약 for문 들어가기 전에 거른다면 좀 더 빨라질 것. [C++로 풀이] 배달 (최단 경로, 다익스트라, 우선순위 큐를 써야하는 이유)⭐⭐⭐

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

using namespace std;

struct Pos {
    int r;
    int c;
    int dir;
    int turn_count;
};

struct cmp {
    bool operator () (const Pos& p1, const Pos& p2) const {
        return p1.turn_count > p2.turn_count;
    }
};

#define INF 987654321

vector<string> Board;
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };

int M, N;
map<char, Pos> pos_record;
#define alpha first 
#define pos second 

Pos BFS(Pos start, char start_alpha) {
    priority_queue<Pos, vector<Pos>, cmp> q;
    vector<vector<int>> turn_and_check(M, vector<int>(N, INF));
    start.dir = -1;
    start.turn_count = 0;
    q.push(start);
    turn_and_check[start.r][start.c] = 0;

    bool not_first = false;
    while (!q.empty()) {
        Pos now = q.top();
        q.pop();

        if (not_first && Board[now.r][now.c] == start_alpha)
            return { now.r, now.c };
        not_first = true;

        for (int i = 0; i < 4; ++i) {
            int nextR = now.r + dr[i];
            int nextC = now.c + dc[i];
            int nextDir = i;
            int next_turn_count = now.turn_count;
            if (now.dir != -1 && now.dir != nextDir)
                next_turn_count++;

            if (nextR < 0 || nextR >= M || nextC < 0 || nextC >= N)
                continue;
            if (next_turn_count >= 2)
                continue;
            if (Board[nextR][nextC] != '.' && Board[nextR][nextC] != start_alpha)
                continue;
            if (turn_and_check[nextR][nextC] >= next_turn_count) {
                q.push({ nextR, nextC, nextDir, next_turn_count });
                turn_and_check[nextR][nextC] = next_turn_count;
            }
        }
    }
    return { -1, -1 };
}

string solution(int m, int n, vector<string> board) {
    string answer = "";
    M = m;
    N = n;
    Board = board;

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (board[i][j] >= 'A' && board[i][j] <= 'Z')
                pos_record[board[i][j]] = { i, j };

    while (true) {
        bool canRemove = false;
        for (auto& letter : pos_record) {
            char start_alpha = letter.alpha;
            Pos start = letter.pos;
            Pos dest = BFS(start, start_alpha);
            if (dest.r != -1 && dest.c != -1){
                canRemove = true;
                Board[start.r][start.c] = '.';
                Board[dest.r][dest.c] = '.';
                answer += start_alpha;
                pos_record.erase(start_alpha);
                break;
            }
        }

        if (canRemove)
            continue;

        if (pos_record.empty())
            return answer;
        else
            return "IMPOSSIBLE";
    }
}

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️