[백준] 14890번 경사로

문제 정의

한 행 또는 한 열의 한쪽 끝에서 다른쪽 끝까지 지나갈 수 있는 길의 개수를 구하는 문제이다. 주어진 조건에 맞춰서 경사로를 세워서 길을 지나가게 할 수 있다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14890) 

문제 풀이

일단 N의 범위가 2에서 100이므로 꽤 큰 편이다. 우선 다 같은 수를 가지는 한 행, 한 열의 경우는 경사로가 필요없이 지나갈 수 있는 길이므로 for문을 통해 간단히 체크를 할 수 있다. 체크를 하는 과정에서 만약 같은 높이가 아니라 낮아지거나 or 높아진다면 그 때 경사로를 놓아본다. 경사로의 길이가 L이므로 한 칸씩 높이를 보면서 L만큼 길이가 있고, 경사로를 통해 지나갈 수 있는 길이 되는지를 판단할 수 있다. 이 문제를 단순히 모든 조건을 검사하도록 구현을 했었다가 틀렸습니다만 왕창 받았었다. 한 행으로 쭉 또는 한 열로 쭉 탐색을 하고, 만약 진행하고 있던 길에서 경사가 생기면 경사로를 놓기 시작하면서 경사로를 얼마나 놓았는지까지 파라매터를 통해서 전달을 해주어서 지나갈 수 있는 길로 만들어 간다.

코드

void xDFS(int i, int j,int past, int cnt) //가로줄 탐색

{

if(j == N-1 && (cnt == L || cnt == 0)){ //지나갈 수 있는 길이라면

road++;

return ;

}

if(cnt != 0 ) // 경사로 쌓고 있는중이면

{

if(cnt == L){ // 경사로 쌓임

if(map[i][j] == map[i][j+1]) //이부분

return xDFS(i, j+1, 0, 0);

else if(map[i][j]-1 == map[i][j+1]) //다음칸이 또 작으면

return xDFS(i, j+1, 0, 1);

else

return ;

}

if(map[i][j] == map[i][j+1]){ //계속해서 쌓기가능

return xDFS(i, j+1, 0, cnt+1);

}

else 

return ; //쌓지못하니까 종료

}

else{

if(map[i][j] == map[i][j+1])

xDFS(i, j+1, past+1, 0); //지나온 길 하나 추가

else if(map[i][j] == map[i][j+1]-1)

{

if(past+1 >= L && cnt == 0)

return xDFS(i, j+1, 0, 0);

}

else if(map[i][j]-1 == map[i][j+1]) //다음칸이 더 작으면

{

return xDFS(i, j+1, 0, 1); //경사로 쌓기 시작

}

}

}