[알고리즘] 상하좌우 탐색, 특정 경로(경로지정)의 영역 탐색 TIP🌟

참고할 문제들

1. [백준 14500] 테트로미노
2. [백준 15683] 감시

상하좌우 탐색

private static int dx[] = {0, 0, 1, -1};
private static int dy[] = {-1, 1, 0, 0};

길찾기와 같이 현재 좌표에서 상하좌우를 모두 탐색해야 하는 알고리즘을 짜는 경우
가장 기본적으로 다음과 같은 static 배열을 선언해주면 훨씬 빠르고 효율적으로 코드를 짤 수 있다.

이렇게 초기 세팅을 하는 기본 원리는 각 dx, dy 배열의 index가 같은 x,y가 한 쌍을 이루어
나중에 좌표를 이동시킬 때 index 값을 바꿔가며 차례대로 아래, 위, 오른쪽, 왼쪽을 탐색하게 된다.(상하좌우 순서는 바뀌어도 무관하다, 알고리즘 따라 다르겠지만)

적용 예시

다음과 같이 nx, ny로 next 좌표를 나타낸 값에 현 위치에서 상하좌우 이동을 한 값을 대입할 수 있다.

 public static void dfs(int x, int y, int sum_value, int length){
        // 길이가 4 이상이면 종료햅줍니다.
        if(length >= 4){
            result = max(result, sum_value);
            return;
        }

        for(int i=0; i<4; i++){
          📌  int nx = x + dx[i];
          📌  int ny = y + dy[i];

            // 지도 넘어가는 경우 검사
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;

            // 방문하지 않은 점이면
            if(check[nx][ny] == false) {

                // 들어가기전 체크해주고
                check[nx][ny] = true;

                dfs(nx, ny, sum_value + a[nx][ny], length + 1);
                // 하나의 탐색을 완료하면 여기로 돌아옵니다.

                // 나올때 체크를 해제합니다.
                check[nx][ny] = false;
            }
        }
    }

특정 경로(경로지정) 영역 탐색

위의 방법을 응용해서 특정 모양(범위) 영역을 탐색할 수 있다.

private static int ex[][] = {{0, 0, 0, 1}, {0, 1, 2, 1}, {0, 0, 0, -1}, {0, -1, 0, 1}};
private static int ey[][] = {{0, 1, 2, 1}, {0, 0, 0, 1}, {0, 1, 2, 1}, {0, 1, 1, 1}};

다음과 같이, 특정 경로를 직접 지정할 때는 이중배열을 활용하여 입력값 좌표를 시작으로 사전에 미리 지정해둔(특정 위치의 영역) 경로로 이동 및 탐색시킬 수 있다.

적용 예시

 public static void check_exshape(int x, int y){

        for(int i=0; i<4; i++){

            Boolean isOut = false;
            int sum_value = 0;

            for(int j=0; j<4; j++){
                📌  int nx = x + ex[i][j];
                📌  int ny = y + ey[i][j];

                if(nx < 1 || nx > n || ny < 1 || ny > m) {
                    isOut = true;
                    break;
                }
                else {
                    sum_value += a[nx][ny];
                }
            }
            if(!isOut) {
                result = max(result, sum_value);
            }
        }

다음 알고리즘은 ㅗ 모양의 테트리스 블록을 회전시킨 4가지 모양의 영역을 탐색하는 알고리즘이다.
각 테트리스의 가장 왼쪽하단에 있는 블록을 (0,0) 기준으로 잡았을 때 (탐색의 시작점이 된다) 상대적인 나머지 블록의 좌표는 그림과 같이 나타난다.
각 테트리스에 해당하는 블록 좌표들을 순서대로 static 이중배열에 선언하면 각 테트리스에 해당하는 영역탐색을 순차적으로 진행할 수 있다.

private static int ex[][] = {{0, 0, 0, 1}, {0, 1, 2, 1}, {0, 0, 0, -1}, {0, -1, 0, 1}};
private static int ey[][] = {{0, 1, 2, 1}, {0, 0, 0, 1}, {0, 1, 2, 1}, {0, 1, 1, 1}};

따라서 ex, ey각 배열의 행은 각 테트리스 한 개를 의미하며 각 행의 열은 각 테트리스의 탐색해야하는 4개의 블록의 좌표를 의미한다.
이 때 탐색의 시작점인 가장 왼쪽하단에 있는 블록은 항상 (0,0)으로 시작한다.

깊이우선탐색(길찾기) 응용

특정 영역/경로를 탐색해야 하는데 해당 경로나 영역이 깊이우선탐색의 패턴을 가지고 있다면 위의 방법대로 하나하나 특정 경로를 지정해주는 것보다 깊이우선탐색을 활용하는 것이 훨씬 더 쉽게 코딩할 수 있는 방법이다.

🎮테트리스 모양의 영역 탐색

위의 블록들을 잘 살펴보면 ㅗ 모양의 블록을 제외한 나머지 블록들은 모두 회전, 대칭시 깊이우선탐색으로 탐색이 가능하다는 특징이 있다.

위의 그림을 보면 흰색 (가운데 블록)을 시작으로 깊이가 4인 깊이 우선 탐색(길찾기)를 진행했을 때 분홍색 부분을 제외한 색이 칠해져있는 부분이 탐색의 범위가 된다.
여기서 주목할 점은 위의 테트리스 모양을 회전, 대칭 시키면 모두 깊이가 4인 길찾기 경로가 되며 그 경로가 색칠된 부분 모두를 포함하고 있다.

이 경우 굳이 위의 방법처럼 하나하나 블록의 모양에 해당하는 경로를 탐색하는 것이 아니라 단순히 깊이우선탐색으로 탐색하는 것이 빠르고 현명하다.

특정 방향으로 쭉 나아가기

이 문제 에서 구현 방법을 헤매다가 결국 못찾아서 정리한다. 다음에는 시뮬레이션 문제도 뚝딱 풀 수 있었으면 좋겠다 😭
문제에서 내가 쉬운 구현을 위해 끙끙 머리를 싸맨 부분은 바로 cctv 마다 방향을 설정해서 방향마다 함수를 따로 주지 않고 하나의 함수만으로도 구현이 어떻게 가능하냐는 점이였다.
평소같으면 무식하게 각각 함수 따로 짰을 거지만 특정 경로 지정을 위에서 학습한 나는 뭔가 특정 경로를 얘도 사전에 줄 수 있을텐데 라는 추상적인 생각만 떠올랐다.

결과적으로는 거시적인 아이디어는 맞았지만 구체화하지 못했으니,,ㅎㅎ 의미가 없어졌지만
그래도 정리하면서 좀 더 특정 범위 탐색의 구현을 체득하면 언젠가는 유연하게 쓸 수 있겠지! 😢

솔루션은 다음과 같다.

 static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1}; // 방향
    static int[][][] ccDir = { // 각 cctv가 볼 수 있는 영역(회전)
            {{0}},
            {{1}, {2}, {3}, {0}}, // 1번 cctv
            {{1, 3}, {0, 2}}, // 2번 cctv
            {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, // 3번 cctv
            {{0, 1, 3}, {0, 1, 2}, {1, 2, 3}, {2, 3, 0}}, // 4번 cctv
            {{0, 1, 2, 3}}, // 5번 cctv
    };

상하좌우 방향이 그대로 활용되는 만큼 평소 상하좌우 정의 방식 대로 dr과 dc를 정의한다
그 후, 각 상하좌우의 index가 결국 dr,dc의 0,1,2,3 index이니 이를 활영해서 ccDir을 설정하면 된다

이 아이디어를 못내서 끙끙대다니 ㅠㅠㅠ 다음에는 꼭 성공하리라...!!

해당 코드의 활용은 다음과 같이 할 수 있다.

 private static void process(int idx, int remain, int[][] map) {
        
        // 모든 CCTV의 감시 영역을 확인했다면
        if(idx == ccCnt) {
            // 사각 지대의 최소 크기 갱신
            res = Math.min(res, remain);
 
            return;
        }
        
        int[][] newMap = new int[N][M];
        copy(newMap, map);
        
        // 각 CCTV를 확인
        CCTV cc = cctvs[idx];
        
        // 해당 CCTV가 90도씩 회전하며 감시
        for (int j = 0; j < ccDir[cc.type].length; j++) {
            // 해당 CCTV가 감시할 수 있는 방향으로 감시
            int check = 0;
            // 현재 상태에서 감시할 수 있는 방향
            for (int k = 0; k < ccDir[cc.type][j].length; k++) {
                int d = ccDir[cc.type][j][k];
                check += observation(cc.r, cc.c, d, newMap);
            }
            
            process(idx + 1, remain - check, newMap);
            // 다른 방향으로도 확인해보기 위해 map 상태를 되돌리자.
            copy(newMap, map);
        }
        
    }
    
    private static int observation(int r, int c, int d, int[][] map) {
        
        // 감시할 수 있는 영역의 수
        int cnt = 0;
        
        while(true) {
            
            r += dr[d];
            c += dc[d];
            
            // 범위를 벗어나거나 벽이 있다면
            if(r < 0 || r >= N || c < 0 || c >= M || map[r][c] == 6) return cnt;
            // 다른 CCTV가 있거나 이미 감시된 영역일 경우 pass
            if((map[r][c] >= 1 && map[r][c] <= 5) || map[r][c] == -1) continue;
            // 빈 칸일 경우
            map[r][c] = -1;
            cnt++;
        }
        
    }

다시 한 번 정리하자면 이 문제의 핵심은 일단 dr, dc의 상하좌우를 위와 같이 설정한 뒤
각 index인 0,1,2,3을 상하좌우 처럼 활용해서 적용했다는 점이다.