[Baekjoon - 10789] 가상 키보드 입력

난이도: Platinum IV

 

태그

• Breadth First Search (In 2D grid)

 

풀이

1. 그래프를 정의해보자.

정점은 튜플 \( (r, c, i) \) = \( i \)개의 글자를 쓴 뒤 \( (r, c) \) 위치로 오는 경우 로 잡고,

간선은 각 \( (r, c) \)에서 상/하/좌/우/선택 중 하나의 키를 누를 때 가게 되는 위치에 연결하면 됩니다.

선택의 경우, 실제로 맞는 글자일 때만 연결해야겠죠.

 

문제의 답은 \( (1, 1, 0) \)에서 출발해서 \( (*, *, |S|) \)로 가는 최단 경로가 됩니다.

 

2. 시간복잡도 / 공간복잡도에 대한 걱정

시간복잡도와 공간복잡도 모두 \( O(NM|S|) \)가 됩니다.

AC를 받아도, TLE/MLE를 받아도 딱히 할 말은 없는 복잡도죠.

 

3. 구현 디테일

\( (r, c, i) \)에서 상/하/좌/우 로 이동할 때, 매번 계산하는 건 시간 낭비입니다.

// 게다가 이건 복잡도에 \( O(N) \)을 곱해버리는, 무서운 행동입니다.

대신, \( (r, c) \)에서 갈 수 있는 4개의 칸을 미리 전처리 한 뒤 그걸 사용해야겠죠.

 

4. 코드

char mp[52][52];
pi2 mov[52][52][4];
 
int dis[52][52][10020];
 
void Main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){ cin >> mp[i][j]; }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int d = 0; d < 4; d++){
                int y = i, x = j;
                while (1 <= y && y <= n && 1 <= x && x <= m){
                    if (mp[y][x] != mp[i][j]){ mov[i][j][d] = {y, x}; break; }
                    y += dy[d]; x += dx[d];
                }
            }
        }
    }
    string s; cin >> s; s += "*"; int sl = s.size();
    memset(dis, -1, sizeof(dis)); dis[1][1][0] = 0;
    queue<pi3> q; q.push({ {1, 1}, 0 });
    while (!q.empty()){
        pi3 p = q.front(); q.pop();
        int y = p.fr.fr, x = p.fr.sc, si = p.sc;
        //cout << "BFS " << y << ' ' << x << ' ' << si << " = " << dis[y][x][si] << endl;
        if (si == sl){ cout << dis[y][x][si]; return; }
        for (int d = 0; d < 4; d++){
            int yy = mov[y][x][d].fr, xx = mov[y][x][d].sc;
            if (yy == 0){ continue; }
            if (dis[yy][xx][si] != -1){ continue; }
            q.push({ {yy, xx}, si }); dis[yy][xx][si] = dis[y][x][si]+1;
        }
        if (s[si] == mp[y][x]){
            if (dis[y][x][si+1] != -1){ continue; }
            q.push({ {y, x}, si+1 }); dis[y][x][si+1] = dis[y][x][si]+1;
        }
    }
}