[기본 알고리즘/완전탐색] 격자에서의 완전탐색

완전탐색은 기본적으로 두 가지 방식이 있습니다.

1. for loop을 이용한 완전탐색
2. 재귀함수를 이용한 완전탐색 (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() 방법 두 가지를 비교한 연산 결과입니다.

위 : Math.max(), 아래 : priorityQueue