[C++] [CSES] Grid Paths (Introductory Problems)

CSES의 열 아홉번째, 마지막 ! 문제입니다.

introductory problems 라고 하지만 대장문제 느낌이 물씬 납니다.

백트래킹에서 pruning(가지치기)를 똑똑하게 하면 속도를 천 배나 올릴 수 있다는 것을 알 수 있는 멋진.. 문제입니다.

시간을 줄이지 못해 책에서 최적화하는 방법을 알게 되었습니다.

 

Task

 

There are 88418 paths in a 7×7 grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left) and R (right).

For example, the path

corresponds to the description DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD.

You are given a description of a path which may also contain characters ? (any direction). Your task is to calculate the number of paths that match the description.

Input

The only input line has a 48-character string of characters ?, D, U, L and R.

Output

Print one integer: the total number of paths.

Example

Input:
??????R??????U??????????????????????????LD????D?

Output:
201

 

Code

#include<bits/stdc++.h>
using namespace std;
string s;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int ans, vis[10][10];

int go(int y, int x, int cur){
    if (y == 7 && x == 1) return cur==48;
    if (cur == 48) return 0;

    if (vis[y][x+1]&&vis[y][x-1]&&!vis[y-1][x]&&!vis[y+1][x]) return 0;
    if (!vis[y][x+1]&&!vis[y][x-1]&&vis[y-1][x]&&vis[y+1][x]) return 0;

    int ret = 0;
    vis[y][x] = 1;

    if (s[cur] != '?'){
        int ny = y, nx = x;

        if(s[cur]=='U') ny--;
        else if(s[cur]=='D') ny++;
        else if(s[cur]=='L') nx--;
        else nx++;

        if (ny>=1 && nx>=1 && ny<=7 && nx<=7 && !vis[ny][nx])
            ret = go(ny, nx, cur + 1);
    }
    else{
        for (int i=0;i<4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny<=0||nx<=0||ny>7||nx>7||vis[ny][nx]) continue;
            ret += go(ny, nx, cur + 1);
        }
    }
    vis[y][x] = 0;
    return ret;
}
int main(){
    cin >> s;
    for(int i=0; i<9; i++){
        vis[0][i] = 1;
        vis[8][i] = 1;
        vis[i][0] = 1;
        vis[i][8] = 1;
    }
    vis[1][1] = 0;
    ans = go(1, 1, 0);
    cout << ans;
}

생각해야 하는 것

• Brute Force로 구해야 하는 것은 맞지만, 아무런 최적화도 하지 않으면 780억번의 함수호출이 된다고 합니다. 이는 일반적인 컴퓨터에서 483초가 걸리며, 1초안에 답을 구해야 하는 저희에게는 택도 없는 방법입니다.
• 시간을 획기적으로 줄일 수 있는 최적화 방법은 위의 go 함수 4 ~ 5번째 줄 부분입니다.
• 책에서 약간의 intelligence를 추가하면 된다는 표현이 있었는데, 정말 그런 것 같습니다.
• 어느 위치에서든 앞쪽이 막혀있고 양 옆에 모두 방문할 수 없으면 함수를 종료하는 코드입니다. (뒷쪽에서 현재 위치로 왔을 것이기 때문에 뒷쪽은 방문처리 되어있음)
• 자세히 말씀드리자면, 경로는 뱀처럼 지나온 길을 방문하면서 진행되기 때문에 앞이 막혀있고, 양 옆이 뚫려있다면 어느 쪽으로 가든지 다른 쪽은 방문을 끝까지 못한다는 의미입니다. 그림으로 그것을 알 수 있습니다.
• 현재 위치에서 옆쪽 중 어느곳을 방문하든지 다른쪽을 방문하지 못하고 함수를 종료할 것임을 알 수 있습니다.
• 위 처리를 통해서 483초 -> 0.73초(CSES 사이트 기준)로 약 1000배 빠른 코드를 작성할 수 있습니다!

드디어 CSES의 Introductory Problems 시리즈를 끝냈습니다!!

다음 토픽인 Sorting and Searching 부터 DP, Graph, Tree 등 문제들도 꾸준히 업로드할 예정입니다.