CS-STUDY/자료구조 & 알고리즘
[기본 알고리즘/완전탐색] 격자에서의 완전탐색
HwangJerry
2023. 9. 28. 15:36
완전탐색은 기본적으로 두 가지 방식이 있습니다.
- for loop을 이용한 완전탐색
- 재귀함수를 이용한 완전탐색 (backtracking)
기본적으로 알고리즘 문제를 풀 때, 시간복잡도를 알아봤을 때 완전탐색으로 풀 수 있는 문제라면 완전탐색으로 푸는게 일반적인 접근입니다.
이번에는 for loop을 이용한 단순한 완전탐색에 대하여 알아보려고 합니다. 격자에서의 완전탐색 문제를 예로 들어서 살펴보겠습니다.
이 문제는 전형적인 for loop 완전탐색 문제입니다. 왜냐하면 n이 3 이상 20 이하의 자연수이기 때문이죠.
n이 20 이하의 자연수라면 for loop 완전탐색 로직을 구상한다고 할 때, 기준점을 선정하는 로직도 이중 루프, 그리고 3x3을 탐색하는 로직도 이중 루프라고 할 때, 시간복잡도가 O(n^2) 인데, 이 경우 정말 최대로 잡아도 연산 횟수가 3600번 정도에 불과합니다. 따라서 완전탐색을 써도 전혀 무리가 없는 것이죠.
O(n^2) 기준으로 n이 1만 이하라면 완탐을 사용할 때에는 일반적으로 큰 무리가 없습니다. 1000ms내로 들어오니까요!
public class 최고의33위치 {
private static int n;
private static int[][] arr;
private static Queue<Integer> pq = new PriorityQueue<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
arr = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// int max = Integer.MIN_VALUE;
for (int i = 0; i < n-2; i++) {
for (int j = 0; j < n-2; j++) {
int res = 0;
for (int k = 0; k < 3; k++) {
for (int l = 0; l < 3; l++) {
res += arr[i+k][j+l];
}
}
pq.add(-res);
// max = Math.max(max, res);
}
}
// System.out.println(max);
System.out.println(-pq.poll());
}
}
풀이 로직에서는 math.max()를 쓰는 방법도 있겠지만, 저는 우선순위 큐를 활용하였습니다. 저의 경우에는 자료구조를 활용하여 최대값을 추출하는 것을 좋아하는데요. 매번 연산을 수행해야하는 Math.max()에 비해 자료구조를 활용하여 구현하면 메모리를 조금 더 쓰더라도 효율적으로 연산을 수행할 수 있기 때문입니다.
실제 priority queue와 math.Max() 방법 두 가지를 비교한 연산 결과입니다.