dfs와 그리디 알고리즘이 합쳐진 문제이다.
왼쪽에서 오른쪽으로 이동을 하는데 왼쪽의 R개의 점에 대해서 다 탐색을 해봐야 한다.
여기서 그리디를 적용해야 하는데 길이 겹치면 안되기 때문에 길 하나를 찾아도 최대한 나머지 길들에 영향을 주지 않아야 한다.
즉, 위에서부터 (1,1)부터 (R,1)까지 R번의 dfs를 도는데 최대한 위로 가야 아래쪽에서 영향을 안 받는다.
오른쪽 위, 오른쪽, 오른쪽 아래 순으로 탐색을 해 나가면 된다.
int main()
{
scanf("%d %d",&R,&C);
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
char t;
scanf(" %c",&t);
if(t=='.') arr[i][j] = 1;
if(t=='X') arr[i][j] = 2;
}
}
for(int i=1;i<=R;i++)
{
dfs(i,1);
}
printf("%d",ans);
}arr 배열 안에 건물의 상태를 담고, dfs를 왼쪽 시작점들에 대해서 탐색한다.
int path[504];
int wx[3]={-1,0,1},wy[3]={1,1,1};
bool dfs(int x, int y)
{
arr[x][y]=2;
if(y==C)
{
//for(int p=1;p<=C;p++)
//{
// arr[path[p]][p]=2;
//}
ans++;
return true;
}
path[y]=x;
for(int n=0;n<3;n++)
{
int nx = x+wx[n];
int ny = y+wy[n];
if(nx<=0 || ny<=0 || nx>R || ny>C) continue;
if(arr[nx][ny]==1)
{
if(dfs(nx,ny)) return true;
}
}
return false;
}문제 해결의 메인 부분인 dfs 함수 부분이다.
path에 탐색을 하면서 지난 점들을 담고, 끝에 도달했을 때 path에 담긴 점들을 arr 배열에 표시하는 식으로 했다.
근데 이렇게 하니까 시간초과가 뜬다.
생각해보니까 어차피 위에서부터 탐색하니까 실패한 경로의 점들은 아래에서 탐색을 할 때도 지날리 없다.
그래서 그냥 성공했을 때 해당 경로를 처리하는게 아니라 탐색하면서 지나는 모든 점들을 처리해도 된다.
#include<stdio.h>
int arr[10004][504];
int R,C;
int ans = 0;
int path[504];
int wx[3]={-1,0,1},wy[3]={1,1,1};
bool dfs(int x, int y)
{
arr[x][y]=2;
if(y==C)
{
//for(int p=1;p<=C;p++)
//{
// arr[path[p]][p]=2;
//}
ans++;
return true;
}
path[y]=x;
for(int n=0;n<3;n++)
{
int nx = x+wx[n];
int ny = y+wy[n];
if(nx<=0 || ny<=0 || nx>R || ny>C) continue;
if(arr[nx][ny]==1)
{
if(dfs(nx,ny)) return true;
}
}
return false;
}
int main()
{
scanf("%d %d",&R,&C);
for(int i=1;i<=R;i++)
{
for(int j=1;j<=C;j++)
{
char t;
scanf(" %c",&t);
if(t=='.') arr[i][j] = 1;
if(t=='X') arr[i][j] = 2;
}
}
for(int i=1;i<=R;i++)
{
dfs(i,1);
}
printf("%d",ans);
}전체 코드이다.
그리디랑 dfs만 적절하게 잘 쓰면 쉽게 해결될 수 있는 문제였다.
