프로그래머스 미로탈출명령어 c++ // dfs 가지치기 방법, dfs중복방문 방법, dfs 시간복잡도 계산방법

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

프로그래머스

1. dfs중복방문 방법

그냥 visit처리안하고

depth==k일때 리턴하면 된다.

 

2. dfs 시간복잡도 계산방법

dfs(0)

:dfs(상) dfs(하) 좌 우

dfs1번당 자식4개 생김

깊이:k

ex)k==2일때, 자식==16(4^2)

복잡도 : 4*4*4*4*4(깊이만큼) == 4^k승

 

3.  dfs 가지치기 방법

1. 사전순으로 dy,dx정함 -> 첫답이 최적해임 -> 첫답을 찾았으면 fin=true 후 dfs종료함

2. 남은이동횟수 < 목표까지거리 -> 도달불가

3. 남은이동횟수와 목표까지거리 의 차이가 홀수다 -> 목표지점에 도달불가능함(남은이동횟수를 모두 다 써야하므로) 

ex) 남은이동횟수 : 1, 목표까지의거리 : 0 -> ??? 불가함, 그옆으로 가야됨

if(fin) return;
int dist=get_dist(x,y,r,c);
if(k-depth<dist) return; //제한-현재깊이 == 남은이동(가능)횟수 < 목표까지거리 -> 도달불가능
if((k-depth-dist)%2==1) return; 
//남은이동(가능)횟수 >= 목표까지거리인 경우 중에서
//남은이동(가능)횟수 와 목표까지거리 차이가 홀수 -> 목표지점 옆칸만갈수있음 -> 불가능

 

4. 전체코드

#include <bits/stdc++.h>
using namespace std;


char a[54][54];
int vis[54][54],vis2[54][54],ret,fin;
int dx[]={1,0,0,-1}; //d l r u
int dy[]={0,-1,1,0};
char dc[]={'d','l','r','u'};
string answer="impossible";
vector<string> v;

int get_dist(int x, int y, int a , int b){
    return abs(x-a)+abs(y-b);
}
void dfs(int depth, int n, int m, int x, int y, int r, int c, int k, string s){
    //cout<<x<<" "<<y<<"\n";
    // if(depth==ret){
    //     v.push_back(s);
    //     return;
    // }
    if(fin) return;
    int dist=get_dist(x,y,r,c);
    if(k-depth<dist) return; //제한-현재깊이 == 남은이동(가능)횟수 < 목표까지거리 -> 도달불가능
    if((k-depth-dist)%2==1) return; 
    //남은이동(가능)횟수 >= 목표까지거리인 경우 중에서
    //남은이동(가능)횟수 와 목표까지거리 차이가 홀수 -> 목표지점 옆칸만갈수있음 -> 불가능
    
    if(depth==k){
        if(x==r && y==c) {
        answer=s;
        fin=1; //dlru순탐색 -> 처음답이 최적해임 -> 더이상 탐색안하도록?
        }
        return;
    }
    
    //vis[x][y]=1;
    
    for(int i=0;i<4;++i){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(ny<1 || ny>m || nx<1 || nx>n) continue;
        if(vis[nx][ny]) continue;
        
        dfs(depth+1, n,m,nx,ny,r,c,k,s+dc[i]);
        //vis[ny][nx]=0;
    }
    return;
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
    
    if(k-get_dist(x,y,r,c)%2==1) return answer;
    dfs(0,n,m,x,y,r,c,k,"");
    
    return answer;
}