[c++] BOJ 17244 :: 아맞다우산

문제

아맞다 우산 문제 바로가기

경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다.

"아 맞다 우산!!!"

경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다.

외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다.

평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다.

경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다.

경재 씨를 위해 집을 위에서 바라본 모습과 챙겨야 할 물건들의 위치들을 알고 있을 때, 물건을 모두 챙겨서 외출하기까지 최소 몇 걸음이 필요한지 구하는 프로그램을 작성하자.

 

풀이

• BFS 순회 문제
• 메모이제이션을 어떻게 할 것인가가 관건
  • 최대 5개의 물건이니 bitmap 사용

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std;

int map[51][51];
int direction[4][2] = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };
int visitedPath[51][51];
unordered_set<int> visitedProduct[51][51];
int POW[5] = { 1, 10, 100, 1000, 10000 };
vector<pair<int, int>> productList;

struct Node {
    int row;
    int col;
    int path;
    int productList = 0;
    Node(int r, int c, int p) {
        row = r; col = c; path = p;
    }
};


int main() {
    // S에서 모든 X를 거쳐 E
    fill(&visitedPath[0][0], &visitedPath[50][51], 1e9);

    int N, M;
    cin >> N >> M;

    pair<int,int> start; pair<int, int> end;
    for (int i = 0; i < M; i++) {
        string str; cin >> str;
        for (int j = 0; j < str.size(); j++) {
            map[i][j] = str[j];
            if (map[i][j] == 'S') {
                start = make_pair(i, j);
            }
            else if (map[i][j] == 'E') {
                end = make_pair(i, j);
            }
            else if (map[i][j] == 'X') {
                productList.push_back(make_pair(i, j)); // X를 0~4로 매핑
            }
        }
    }

    int result = 0;
    for (int i = 0; i < productList.size(); i++) {
        // 미리 저장해두기 (product 다 채웠을 때)
        result += POW[i];
    }

    queue<Node*> que;
    que.push(new Node(start.first, start.second, 0));
    visitedPath[start.first][start.second] = 0;

    while (!que.empty()) {
        auto pos = que.front(); que.pop();

        if (pos->row == end.first && pos->col == end.second) {
            if (pos->productList == result) {
                cout << pos->path;
                return 0;
            }
        }

        for (int i = 0; i < 4; i++) {
            int r = pos->row + direction[i][0];
            int c = pos->col + direction[i][1];

            if (r < 0 || r >= M || c < 0 || c >= N) {
                continue;
            }
            if (map[r][c] == '#') {
                continue;
            }

            Node* tmp = new Node(r, c, pos->path+1);
            tmp->productList = pos->productList;

            if (map[r][c] == 'X') {
                int idx = 0;
                for (int i = 0; i < productList.size(); i++) {
                    if (r == productList[i].first && c == productList[i].second) {
                        idx = i;
                        break;
                    }
                }
                int haveProduct = (tmp->productList / POW[idx]) % 10;
                if (haveProduct == 0) {
                    tmp->productList += POW[idx];
                }
            }
            auto sameProductAgain = (visitedProduct[r][c].find(pos->productList) != visitedProduct[r][c].end());
            if ((visitedPath[r][c] <= pos->path+1) && sameProductAgain) {
                // 더 큰 path로 들르는데, 들른 product가 같으면 건너뛰기
                continue;
            }

            que.push(tmp);
            visitedPath[r][c] = tmp->path;
            visitedProduct[r][c].insert(tmp->productList);
        }
    }
}

 

개선

• pow는 미리 계산한 뒤 사용
• 코드 넘 길어서 간단하게 해야함

 

결과

아이디	메모리	시간	언어
gmldms784	11172	40	C++17 / 수정