[프로그래머스/c++] Level 3: 등굣길

somyeong·2022년 5월 8일
0

프로그래머스

목록 보기
7/14

문제 링크 - https://programmers.co.kr/learn/courses/30/lessons/42898#qna

🌱 문제


🌱풀이 및 코드

//학생때 배운 최단경로 공식을 이용
#include <string>
#include <vector>
#include <iostream>
#define mod 1000000007

using namespace std;
bool p[101][101]; // 물에잠긴 좌표는 true
int d[101][101];
bool row_flag;
bool col_flag;

//n이 행, m이 열
int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    //물에잠긴 지역 처리
    for(int i=0; i<puddles.size(); i++){
        int x=puddles[i][1];
        int y=puddles[i][0];
        
        p[x][y]=true;
    }    
    
    //시작좌표 0, 시작좌표를 제외한 첫번째 행과 첫번째열을 1로 초기화
    d[1][1]=0;
    //첫번째 행 초기화
    for(int i=2; i<=m; i++){
        if(p[1][i]){// p[1][i]지점이 물에잠겼으면 그 지점과, 그 이후 지점은 최단경로로 갈 수 없으므로 0으로 초기화
            d[1][i]=0;
            row_flag=true;
        }
        if(row_flag==true)
            d[1][i]=0;
        else
            d[1][i]=1;
    }
    
    //같은 방식으로 첫번째 열 초기화
     for(int i=2; i<=n; i++){
        if(p[i][1]){
            d[i][1]=0;
            col_flag=true;
        }
        if(col_flag==true)
            d[i][1]=0;
        else
            d[i][1]=1;
    }
    
 
    //최단경로 공식 적용
    for(int i=2; i<=n; i++){
        for(int j=2; j<=m; j++){
            if(p[i][j]==true){
                d[i][j]=0;
                continue;
            }
            d[i][j]=(d[i-1][j]+d[i][j-1])%mod;
        }
    }
    
    
    return d[n][m];
}
profile
공부한 내용 잊어버리지 않게 기록하는 공간!

0개의 댓글