[JAVA] 알파벳 ::: 그래프탐색,DFS,백트래킹

[ 문제 ]

https://www.acmicpc.net/problem/1987

 

 

[ 제출코드 ]

 

 

 

[ 풀이 ]

주어진 맵에서 알파벳을 탐색하여, 서로 다른 알파벳을 방문하는 경로의 최댓값을 구합니다.

깊이 우선 탐색(DFS) 방식을 사용했습니다.

 

 

 

[ 시간 복잡도 & 공간 복잡도 ]

DFS 탐색

• DFS에서 모든 가능한 경로를 탐색하려고 할 때, 각 지점에서 4개의 방향으로 재귀적으로 탐색합니다. visited 배열을 사용하여 방문한 알파벳을 기록하고, 이미 방문한 알파벳을 다시 방문하지 않도록 처리합니다.
• visited 배열의 크기는 최대 26 (`A`부터 `Z`까지)입니다. DFS에서 탐색하는 경로는 각 위치에서 최대로 26개의 알파벳을 방문할 수 있습니다.
• 각 위치에서 4방향으로 탐색할 수 있지만, 방문한 알파벳을 다시 방문하지 않기 때문에 탐색 가능한 경로의 수는 O(R * C)입니다. R은 행의 수, C는 열의 수입니다. 따라서, 전체 DFS의 시간 복잡도는 O(R * C)입니다.

입력 처리

• 입력을 받는 과정에서 맵을 읽는 데 시간이 소요됩니다. 맵의 크기는 R * C이므로, 이 입력 처리의 시간 복잡도는 O(R * C)입니다.

따라서, 전체 시간 복잡도는 O(R * C)입니다.

 

 

맵 저장 공간

• 맵은 2D 배열 map[R][C]로 저장됩니다. 이 배열의 크기는 R * C이므로, 공간 복잡도는 O(R * C)입니다.

방문 기록 배열

• visited 배열은 알파벳의 수에 맞게 26개의 원소를 저장합니다. 따라서 공간 복잡도는 O(26), 즉 O(1)로 볼 수 있습니다.

재귀 스택

DFS가 재귀적으로 호출되므로, 최악의 경우 모든 경로를 탐색하려면 재귀 깊이가 R * C까지 갈 수 있습니다. 따라서, 재귀 스택에 필요한 공간 복잡도는 O(R * C)입니다.

전체 공간 복잡도는 O(R * C)입니다.

결론

• 시간 복잡도: O(R * C)
• 공간 복잡도: O(R * C)

=> 주어진 맵의 크기인 R * C에 비례하여 증가하는 시간 및 공간 복잡도를 갖습니다.