프로그래머스_등굣길

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

코딩테스트 연습 - 등굣길 | 프로그래머스

해당 문제는 DP 문제였다. 

목적지 까지 최소 경로의 개수를 구하는데, 바로 한 칸 전의 최소경로의 수들을 더하면 된다.

다만 물 웅덩이는 지나갈 수 없다는 조건이 있었는데, 물 웅덩이의 경우에는 최소 경로를 0 으로 고려하여 넘어가면 된다.

 

그런데 처음에 DFS로 문제를 풀어보니 꽤 복잡하였다. 그리고 시간복잡도도 터져버릴 정도로 좋지 않았다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 10000000
using namespace std;

int min_cnt = 0;
int min_dist = MAX;
pair<int ,int> dest;

// 동남서북
int dx[4] ={0,1,0,-1};
int dy[4] ={1,0,-1,0};

void print(pair<int,int> p){
    cout<<p.first<<" "<<p.second<<"\n";
}

// 완전탐색
void dfs(vector<vector<int>> p, pair<int,int> now, int cnt){
    // 백트랙킹(그만 방문)
    if(cnt > min_dist )
        return;
    
    // 도착 시
    if(now == dest){
        // 최소기록 갱신
        if(min_dist > cnt){
            min_dist = cnt;
            min_cnt = 0;
        }
        // 최소 기록이면
        min_cnt = (min_cnt + 1) % 1000000007; // 경로 수 증가
        return;
    }
    
    
    // 이동(동남서북)
    for(int i=0;i<2;i++){
        pair<int,int> next(now.first + dx[i], now.second + dy[i]);
        // 이동 가능하면
        int can = 1;
        for(int j=0;can==1 && j<p.size();j++){
            if(p[j][0] == next.first && p[j][1] == next.second)
                can = 0; // 불가능
        }
        // 좌표 안 벗어나면
        if(can==1 && next.first>=1 && next.first <= dest.first && next.second >= 1 && next.second <= dest.second )
            dfs(p, next, cnt+1);
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    dest.first = m, dest.second = n;
    dfs(puddles, pair<int,int>(1,1),0);// 탐색
    return min_cnt;
}

그래서 다음의 DP 코드로 완성하였다.

어차피 동쪽, 남쪽 이동만 고려하면 되기에 어렵지 않게 해결할 수 있었다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 10000
using namespace std;
int dx[2] = {0, 1};
int dy[2] = {1, 0};

void print(vector<vector<pair<int,int>>> pv){
    for(int i=1;i<pv.size();i++){
        for(int j=1; j<pv[i].size();j++)
            cout<<pv[i][j].first<<" "<<pv[i][j].second<<"\n";
        cout<<"\n";
    }
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    // <거리, 경로 수>
    vector<vector<pair<int,int>>> g;
    for(int i=0;i<n+1;i++){
        vector<pair<int,int>> temp(m+1,pair<int,int>(MAX,0));
        g.push_back(temp);
    }
    
    // 갈 수 없는 곳 표시
    for(int i=0;i<puddles.size();i++)
        g[puddles[i][1]][puddles[i][0]] = pair<int,int>(-1,-1); // puddle
    
    // 차례로 탐색
    g[1][1] = pair<int,int>(0,1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            // 시작 점 제외
            if(i==1 && j==1)
                continue;
            
            // 웅덩이가 아니라면
            if(g[i][j].first != -1){
                // 이전 것들도 체크(Case 1 왼쪽)
                int c1_i = i-dx[0], c1_j = j-dy[0];
                if(c1_i >= 1 && c1_i <= n && c1_j>=1 && c1_j<=m)
                    if(g[c1_i][c1_j].first != -1){
                        // 최소값이라면 거리 갱신
                        if(g[i][j].first > g[c1_i][c1_j].first+1){
                            g[i][j].first = g[c1_i][c1_j].first+1;
                            g[i][j].second = g[c1_i][c1_j].second;
                        }
                        // 같다면 더하기
                        else if(g[i][j].first == g[c1_i][c1_j].first+1)
                            g[i][j].second = (g[i][j].second + g[c1_i][c1_j].second ) % 1000000007;
                    }
                
                // 이전 것들도 체크(Case 2 위쪽)
                int c2_i = i-dx[1], c2_j = j-dy[1];
                if(c2_i >= 1 && c2_i <= n && c2_j>=1 && c2_j<=m)
                    if(g[c2_i][c2_j].first != -1){
                        // 최소값이라면 거리 갱신
                        if(g[i][j].first > g[c2_i][c2_j].first+1){
                            g[i][j].first = g[c2_i][c2_j].first+1;
                            g[i][j].second = g[c2_i][c2_j].second;
                        }
                        // 같다면 더하기
                        else if(g[i][j].first == g[c2_i][c2_j].first+1)
                            g[i][j].second = (g[i][j].second + g[c2_i][c2_j].second) % 1000000007;
                    }
            }
        }
    }
    return g[n][m].second;
}

참고할만한 풀이

굳이 최소경로를 검사하지 않아도 어차피 바로 왼쪽과 위쪽의 최소 경로가 다음 칸으로 가는 최소경로임을 보장하고 있었다. for문으로 i,j를 차례로 검사하기에 최소 경로 검사가 따로 필요없었고 이에 따라 pair 자료형도 필요 없고 코드가 훨씬 간결해졌다.

 

https://dailyheumsi.tistory.com/25

[프로그래머스] 등굣길

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int dist[101][101] = {0,};
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            // 출발점 제외
            if(i==1 && j==1){
                dist[i][j]=1;
                continue;
            }
            // 갈 수 없는 경우
            bool can = true;
            for(int k=0;can && k<puddles.size();k++)
                if(i==puddles[k][1] && j==puddles[k][0])
                    can = false;
            if(!can)
                dist[i][j]=0;
            
            // 갈 수 있는 경우
            else
                dist[i][j] = (dist[i-1][j] + dist[i][j-1]) % 1000000007;
        }
    }
    
    return dist[n][m];
}