시간복잡도에대해서 생각해볼 수 있는 문제였다.
이문제는 단순한 dfs로 생각 할수도 있다. 그런데 조건 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 때문에 일반적인 dfs로는 풀지 못한다.
왜일까?
ㅁㅁㅁ
ㅁㅁㅁ
ㅁㅁㅁ
이렇게 칸이 있다고 치자, 5번을 움직이는 경우를 살펴볼까?
4방향으로 움직일 수 있으므로 시계방향으로 움직인다 가정하면
처음에 오른쪽칸으로 이동 ->for문 4번
두번째 2,3에서 아래로이동 -> for문 4번
세번쨰 3,3에서 왼쪽으로 이동 ->for문 4번
...
즉 결국 이동할수있는 거리가 5번이면 4^5의 시간 복잡도가 걸린다.
즉 만약 최대 경우가 2500이면 4^2500의 시간이 걸리므로, 대략적으로 1505자리가 나오는데 1억이 9자리라고생각하면 절대 풀수가 없을 것이다.
그러니까 문제에서 주어진 조건으로 어느정도 해결을 해야하는데,
-
힌트는 사전식에 있다.
문자열이 사전순으로 가장 빠른 경로로 탈출해야한다 하였으므로,
4방향 방문을 dlru순으로 방문하는것이다.int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
char addstring[4]={'d','l','r','u'}; -
만약에 내가 이동할수있는 거리 k보다 애초에 시작점과 end지점이 더 먼경우이다.
int remain = abs(x-r)+abs(y-c); 이고 k가 remain보다 작다면 애초에 불가능하다. 왜냐하면 직선거리가 최단거리인데 이 최단거리보다 덜 이동할 수 있기 때문이다.remain > k
-
마지막 조건이 까다로웠는데
내가 이동할수있는 k에서 remain을 뺐을때 나머지가 2의 배수로 남으면 안된다.
왜냐하면, 아까 위의 3*3 map에서 1,1에서 3,3으로 간다고 치자 근데 k가 4이면
아래 아래 오른 오른으로 딱 갈 수 있다. 근데 k가 5이면 절대로 정확히 End지점에
도달 할 수없다.
즉 remain= |3-1|+|3-1|=4이고 k가 5이면 5-4 =1 그리고 1은 2의 배수가 아니므로 무조건 end지점에 도착할 수 없다.(k-remain) % 2!=0
코드
solution
string solution(int n, int m, int x, int y, int r, int c, int k) {
N=n;
M=m;
targetr = r;
targetc = c;
int remain = abs(x-r)+abs(y-c);
if((k-remain) % 2!=0 || remain > k){
answer = "impossible";
}else{
string s="";
dfs(x,y,0,k,s);
}
return answer;
}solution에서 애초에 불가능한 경우 2,3번을 검증하고 가능할 수도 있으면 dfs를 부른다.
void dfs(int x, int y ,int cnt,int k,string s){
if(cnt==k){
if(x==targetr && y == targetc ){
flag++;
answer+=s;
}
return;
}
if(k-cnt<abs(x-targetr)+abs(y-targetc)){
return;
}
for(int i=0;i<4;i++){
if(cnt<k && flag==0){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx>=1 && nx<=N && ny>=1 && ny <=M){
s+=addstring[i];
dfs(nx,ny,cnt+1,k,s);
s.pop_back();
}
}else{
return;
}
}
}dfs는 오히려 간단하다.
일단, cnt는 이동한거리 k는 최대 거리이다. 최대거리까지 갔을때, targetr(r)과 targetc(c)와 동일하다면, 사전순으로 이동하였으므로 이게 정답이다. 그러니까 flag를 ++하고 answer에다가 담아 return한다.
flag를 ++하는 이유는 뒤에 나온다.
그리고, 매 순간마다. 지금 움직일수있는 거리가 남은 거리보다 큰지 확인해야한다.
if(k-cnt<abs(x-targetr)+abs(y-targetc)){
return;
}
이건 생각하기 많이 어려운 로직인데 k-cnt를 빼면 이제 내가 움직일 수 있는 거리가 나온다. 이 거리가 시작점과 끝점의 최대거리보다 작다면, 애초에 도달하지 못하므로 return한다.
이 모든 조건을 검사하고 4방향으로 움직여야한다.
일단 cnt가 k보다 작아야하고 flag가 0이어야한다. 왜냐하면 flag가 1이면 이미 정답을 찾은것이므로 그 나머지 경우를 계산을 할 이유가 없다. 그러므로 if문을 통과하지 못하면 return해준다.
그다음에 다음nx,ny좌표를 구하고 범위검사를 하고, 정답인 s에다가 addstring으로 문자를 더해준다.
그리고 dfs를 나오면, 당연히정답이 아닐테니까. s.pop_back()으로 하나 빼준다.
어? 만약에 정답이어도 return으로 나오는데?? 싶어도 정답일 경우에는 정답 stringn인 s를 answer에다가 이미 옴겨놔서 괜찮다.
전체코드
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int targetr=0;
string answer="";
int targetc=0;
int flag =0;
int N=0;
int M=0;
int dx[4]={1,0,0,-1};
int dy[4]={0,-1,1,0};
char addstring[4]={'d','l','r','u'};
void dfs(int x, int y ,int cnt,int k,string s){
if(cnt==k){
if(x==targetr && y == targetc ){
flag++;
answer+=s;
}
return;
}
if(k-cnt<abs(x-targetr)+abs(y-targetc)){
return;
}
for(int i=0;i<4;i++){
if(cnt<k && flag==0){
int nx = x+dx[i];
int ny = y+dy[i];
if(nx>=1 && nx<=N && ny>=1 && ny <=M){
s+=addstring[i];
dfs(nx,ny,cnt+1,k,s);
s.pop_back();
}
}else{
return;
}
}
}
string solution(int n, int m, int x, int y, int r, int c, int k) {
N=n;
M=m;
targetr = r;
targetc = c;
int remain = abs(x-r)+abs(y-c);
if((k-remain) % 2!=0 || remain > k){
answer = "impossible";
}else{
string s="";
dfs(x,y,0,k,s);
}
return answer;
}