[프로그래머스 고득점 kit] 등굣길 c++ (dp+bfs)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

 

문제 풀이

 

dp[a][b]를 시작점에서 (a,b) 지점까지 도달하는 경로의 가짓수라고 가정하자.

시작점에 1을 넣고(제자리에 있는 것 ==1개의 경로) dfs or bfs로 완전탐색을 수행한다. ( 이때, 아래 or 오른쪽으로만 이동하기에, 왔던 길을 되돌아올 일은 없다.)

 

만약  a,b라는 지점에서 두개의 분기점이 만난다면,  (a-1,b) 와 (a,b-1) 지점이 만나게 된다. (아래 or 오른쪽이라는 조건으로 인해)   

따라서 두개(만나는 지점 기준 위, 왼쪽)의 분기점이 합쳐질 때마다  두 분기점까지의 경로의 가짓수를 합치고, 1개의 분기로 합치면 된다.

 

분기를 합친다는 것이 이해가 어려울 수 있으니, 아래의 그림을 참고하자.

 

 

분기를 합쳤을 때

 

합쳐진 분기는 1개의 가닥으로 진행해야한다.

 

 

분기를 합치지 않았을 때

합쳐진 분기가 여전히 각각 탐색하면 안된다.

 

위 그림과 같이, 분기를 합치지 않는다면, 똑같은 경로의 값이 2번 적용되어 오답이 나온다.

 

 

 

정답 코드

나는 bfs를 통해 고현했다. visit 배열을 구성하는 것으로 이미 방문한 지점을 탐색하는 경우, dp의 값은 추가하되, queue에 해당 지점을 추가하지 않는 것으로, dp 값은 누적하고, 분기는 생성하지 않는 것으로 문제를 해결했다.

#include <string>
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
long long  dp[110][110];
int dr[2]={0,1};
int dc[2]={1,0};
int visit[110][110];
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    queue<pair<int,int>> qu;
    for(auto a:puddles){
        visit[a[1]-1][a[0]-1]=2;
    }
    qu.push({0,0});
    dp[0][0]=1;
    while(!qu.empty()){
        int r=qu.front().first,c=qu.front().second;
        qu.pop();
        for(int i=0;i<2;i++){
            int nr=r+dr[i],nc=c+dc[i];
            if(0>nr||n<=nr||0>nc||m<=nc)continue;
            if(visit[nr][nc]==2)continue;//진입 불가 지점
            dp[nr][nc]+=dp[r][c]%1000000007;
            dp[nr][nc]%=1000000007;
            if(visit[nr][nc]==1)continue;//같은 곳은 1번만 방문(분기점 합치기)
            visit[nr][nc]=1;
            qu.push({nr,nc});
        }
    }
    answer=dp[n-1][m-1];
    return answer;
}