[Leet code - 62] Unique Paths ❌

문제

Input : 정수 m,n

Output : 배열[0][0] 에서 배열[m - 1][n - 1]까지 갈 수 있는 경로의 개수

 

※ 이동은 하단, 우측으로만 가능하다.

 

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

 

$1 \le m,\ n\le 100$

여기서 최소 연산단위는 2차원 배열의 셀로 생각했다.

그렇기 때문에 복잡도의 n은 셀의 총 개수 이므로, $\text{(복잡도)}n = m \times n = 10,000$으로 n을 산정했다.

• $n^2 = 100,000,000$❓
  통과하기 아슬아슬한 복잡도로 제일 후순위로 고려해본다. 
• $n\ log\ n \approx 133,000$✅
  따라서 $n log n$이하의 복잡도 이하를 목표로 풀이한다.

 

해결 계획

내가 아는 길찾기는 DFS, BFS뿐인데, DFS의 복잡도는 이미 고려대상이 아니므로 BFS를 사용하려했다.

 

우선, 하단과 우측으로만 이동이 가능하기 때문에 map[y][x]의 경로의 수는 map[y-1][x] + map[y][x-1]임을 발견했다.

이를 BFS로 어떻게 구현할까 생각하다가, BFS로 노드를 순회할때 값을 다음 노드에 넘겨주면서 큐에 삽입하는 방식을 생각했다.

 

BFS의 특성상 한 레벨이 모두 끝나야만 다음 레벨의 노드가 조회가 되기 때문에,

값이 최종적으로 갱신되기 전에 값이 다른 노드로 전달되버리는 불상사는 일어나지 않을거라고 생각헤서 BFS로 진행했다.

 

 

구현

#define Y first
#define X second
using pii = pair<int,int>;

int uniquePaths(int m, int n) {
    int map[101][101] = {1};
    int visited [101][101] = {0};
    pii nextDir[2] = {{0, 1}, {1, 0}};

    queue<pii> q;
    q.push({0,0});

    while(q.empty() == false)
    {
        pii now = q.front();
        q.pop();

        // 하단과 우측을 큐에 삽입하면서 경우수 더함
        for (const auto& data : nextDir)
        {
            // 다음 노드
            pii next = {now.Y + data.Y, now.X + data.X};

            // 우선 자신의 값을 먼저 넘긴다.
            map[next.Y][next.X] += map[now.Y][now.X];

            // 큐에 삽입할 때만 유효한 칸인지 확인한다.
            if (visited[next.Y][next.X] == true || n<= next.X || m<= next.Y) continue;

            // 큐 삽입
            q.push({next.Y, next.X});
            visited[next.Y][next.X] = true;
        }
    }

    return map[m - 1][n - 1];
}

 

 

되돌아보기

DP

이 문제는 풀긴했으나 VS로 디버깅까지 사용했었고, 너무 오래걸려 실패나 마찬가지다..

심지어 더 나은 방법으로 DP를 사용할 수 있었다.

 

길찾기라는 단어에 꽂혀서 무조건적으로 BFS를 사용했었는데,

실질적 문제는 경로 개수의 누적이였다.

 

그래서 이미 점화식인 dp[y][x] = dp[y-1][x] + dp[y][x-1] 을 찾아놓고도 먼 길을 돌아 갔다..ㅠ

아무튼 다음에는 누적문제에 DP 아이디어를 생각해볼 수 있겠다.

접근 방법

평소에 알고리즘 먼저 생각하고 풀이를 생각했었는데, 뭔가 특정 알고리즘에 틀이 박혀 시야가 좁아지는 느낌이 있다.

그래서 간단한 예제를 먼저 끄적이면서 아이디어를 생각해보는 것도 좋을듯?

 

 

개선 코드

위에서 말했던 DP를 이용해서 풀어 봤다.

int uniquePaths(int m, int n) {

    // 초기 값 설정
    int dp[101][101] ={0};
    for (int y = 0; y < m; ++y)
        dp[y][0] = 1;
    for (int x = 0; x < n; ++x)
        dp[0][x] = 1;

    // 테이블 채우기
    for (int y = 1; y < m; ++y)
    {
        for (int x= 1; x < n; ++x)
        {
            dp[y][x] = dp[y - 1][x] + dp[y][x - 1];
        }
    }

    // Output
    return dp[m - 1][n - 1];
}