[SWEA] 7396 : 종구의 딸이름 짓기

7396 : 종구의 딸이름 짓기

풀이

BFS

(0,0)에서 (n-1,m-1)까지 가는 경로에서 사전순으로 앞선것들을 추가하면된다.

이때 중간경로에서 사전순으로 앞선것만 추가하는게 항상 최종적으로 앞선다는 최소성이 만족된다.

string ans에 (0,0)값을 넣고 (0,0)을 큐에 넣어서 해당 좌표의 아래와 오른쪽을 벡터에 넣는다.

큐가 empty가 되면 vector를 뒤져서 최소값을 찾는다.

최소값을 ans에 추가하고 그리고 최소값과 같은 좌표는 다시 큐에넣는다.

좌표가 n-1,m-1이 될때까지 을 반복한다.

이렇게 풀었는데, 시간초과가 났다.

왜냐하면 큐에서 좌표를 벡터로 옮길때 어떤좌표의 오른쪽과 다음좌표의 아래쪽에서 중복이 발생하기 때문이다.

벡터의 중복을 없애는 코드

vp.erase(unique(vp.begin(), vp.end()), vp.end());를 추가해서 해결했다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        string ans;
        int n, m;
        cin >> n >> m;
        vector<string> v;
        for (int i = 0; i < n; i++) {
            string tmp;
            cin >> tmp;
            v.push_back(tmp);
        }
        ans.push_back(v[0][0]);
        queue<pair<int, int>> q;
        vector<pair<int, int>> vp;
        q.push({0,0});
        while (1) {
            while (!q.empty()) {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                if (x + 1 < n) {
                    vp.push_back({ x + 1,y });
                }
                if (y + 1 < m) {
                    vp.push_back({ x,y + 1 });
                }
            }
            vp.erase(unique(vp.begin(), vp.end()), vp.end());
            if (vp.size() == 0) {
                break;
            }
            if (vp[0].first==n-1 && vp[0].second==m-1) {
                ans.push_back(v[vp[0].first][vp[0].second]);
                break;
            }
            char mChar = v[vp[0].first][vp[0].second];
            for (int i = 1; i < vp.size(); i++) {
                if (mChar > v[vp[i].first][vp[i].second]) {
                    mChar = v[vp[i].first][vp[i].second];
                }
            }
            ans.push_back(mChar);
            for (int i = 0; i < vp.size(); i++) {
                if (mChar == v[vp[i].first][vp[i].second]) {
                    q.push({vp[i].first,vp[i].second});
                }
            }
            vp.clear();
        }
        cout << "#" << tc << ' ' << ans << '\n';
    }
    return 0;
}

Written on April 5, 2019