1987

BFS로 풀다가 메모리 초과가 떠서 DFS로 해결했다.

간단히 재귀함수를 만들어서 해결했는데 속도를 높이고 싶으면 재귀 함수를 사용하지 않고 stack을 이용해서 해결해도 좋을 것 같다.

#include<iostream> #include<cstdio> #include<queue> #include<stack> #include<vector> using namespace std; class Finder{ public: int r, c, sum; bool visited[30]; }; char map[25][25]; int R, C; long long res = 0; void dfs(Finder s, long long walk){ int r = s.r; int c = s.c; int newcost = s.sum+1; res = max(res, walk); if(r-1>=0 && !s.visited[(int)(map[r-1][c]-'A')]){ Finder f; for(int i=0; i<30; i++) f.visited[i]=s.visited[i]; f.visited[(int)(map[r-1][c]-'A')]=true; f.r=r-1; f.c=c; f.sum=newcost; dfs(f, newcost); } if(r+1<R && !s.visited[(int)(map[r+1][c]-'A')]){ Finder f; for(int i=0; i<30; i++) f.visited[i]=s.visited[i]; f.visited[(int)(map[r+1][c]-'A')]=true; f.r=r+1; f.c=c; f.sum=newcost; dfs(f, newcost); } if(c-1>=0 && !s.visited[(int)(map[r][c-1]-'A')]){ Finder f; for(int i=0; i<30; i++) f.visited[i]=s.visited[i]; f.visited[(int)(map[r][c-1]-'A')]=true; f.r=r; f.c=c-1; f.sum=newcost; dfs(f, newcost); } if(c+1<C && !s.visited[(int)(map[r][c+1]-'A')]){ Finder f; for(int i=0; i<30; i++) f.visited[i]=s.visited[i]; f.visited[(int)(map[r][c+1]-'A')]=true; f.r=r; f.c=c+1; f.sum=newcost; dfs(f, newcost); } } int main(){ scanf("%d %d", &R, &C); for(int i=0; i<R; i++) scanf("%s", map[i]); Finder f; f.r = 0; f.c=0; f.sum = 1; for(int i=0; i<30; i++) f.visited[i]=false; f.visited[int(map[0][0] - 'A')]=true; dfs(f, 1); printf("%lld\n", res); return 0; }