(24.11.18) BFS를 활용한 도현의 외각선 탐색

 

---

도형의 외곽선 탐색하기 알고리즘

• 도형의 외곽선을 탐색하면서 가장 짧은 거리를 반환하는 알고리즘
  • 내부로 진입 X

import java.util.*;

class Solution {
    // 방향키
    public int[] dx = {-1,1,0,0};
    public int[] dy = {0,0,-1,1};
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        // 영역 지정 2배 확장
        int[][] map = new int[101][101];
        
        // 주어진 사각형 외각선 1 내부 2 설정하기
        for(int[] rec : rectangle) {
            int leftX = rec[0]*2;
            int leftY = rec[1]*2;
            int rightX = rec[2]*2;
            int rightY = rec[3]*2;
            
            for(int i = leftX ; i <= rightX; i++) {
                for(int j = leftY ; j <= rightY; j++) {
                 if(i == leftX || i == rightX || j == leftY || j == rightY)  {
                     // 외곽선 1 설정
                     if(map[i][j] !=2) map[i][j] = 1;
                 } else {
                    // 내부 2 설정
                     map[i][j] =2;
                 }
                }
            }
        }
        
        
        // visited
        boolean[][] visited = new boolean[101][101];
        
        // bfs
        return bfs(map, visited, characterX*2, characterY*2, itemX*2, itemY*2) / 2;
        
    }
    
    public int bfs(int[][] map, boolean[][] visited, int characterX, int characterY, int itemX, int itemY) {
        // queue 설정
        Queue<int[]> queue = new LinkedList<>();
        
        // 시작 설정
        queue.add(new int[]{characterX, characterY});
        visited[characterX][characterY] = true;
        
        int count = 0;
    
        // 움직이면서 파악
        while(!queue.isEmpty()) {
            int size =  queue.size();
            
            for(int i = 0; i < size; i++) {
                // 현재 노드 = 좌표
                int[] current = queue.poll();
                int currentX = current[0];
                int currentY = current[1];
                
                // 목표점 도달시 종료
                if(currentX == itemX && currentY == itemY) return count;
                
                // 상하좌우 움직이면서 조건에 맞는 좌표 등록
                // 방문을 안한 좌표여야
                // 움직인 좌표 x y 0이상 50이하
                // 다음 조건 : 해당 좌표의 값이 1일 경우
                for(int j = 0 ; j < 4; j++) {
                    int nextX= currentX + dx[j];
                    int nextY = currentY + dy[j];
                    
                    if(nextX >= 0 && nextX <= 100 &&
                      nextY >=0 && nextY <= 100 &&
                      !visited[nextX][nextY] &&
                      map[nextX][nextY] == 1) {
                
                            visited[nextX][nextY] = true;
                            queue.add(new int[]{nextX, nextY});
                        
                    }
                    
                }
             } 
            
            count++;
            
        }
        return -1;
    }
}

• 최단 거리만 탐색하는 알고리즘이기 때문에 BFS 탐색을 사용
  • 방향키로 주변 4방향의 좌표점을 이동하면서 탐색하는 방식
• 외곽선은 1, 내부는 2 그 외는 0으로 설정하기 위한 map을 설정해 외곽선만을 탐색 가능하도록 함
  • 외곽선이 2개 생기더라도 최단거리를 구하는 것이기 때문에 가능

스케일 업 사용

• 도형이나 좌표에 위치해있는 특정 구역에서 외곽선 과 내부가 구분해서 탐색 영역을 분리를 해야할 때 사용
• 50칸의 좌표를 사용하기 때문에 맵의 크기는 스케일업은 2배로하여 0~100 좌표를 사용 map[101][101] 로 사용

외곽선 분리

• 도형의 크기가 작을 경우 ex) [1, 1, 2, 3] 내부와 구분이 어려줘져서 사각형이 겹치기 시작하면 경계 계산이 힘들어짐
  • 따라서 Pixel 조건을 가지고 와서 4개의 점으로 분리하기 위해 각 좌표를 2배로 스케일 업

알고리즘의 효율

• 위의 경우와 유사하게 제일 짧은 거리를 사각형들을 통과하면서 처리를 하거나 빈 공간을 넘어갈 수 있기 때문에 예외 상황에 대한 조건을 더 걸어줄 필요가 없음
  • 방향키로 1 좌표씩 움직일 때, 그 곳이 내부인지 외곽선인지 확실히 할 수 있음

외곽선 겹침 방지

• 각 도형의 경계선을 다른 도형의 내부로 들어가는 경우를 방지

---

항상 알고리즘을 접하다 보면 코드를 짜면서 도형을 점선처럼만 생각을 하기 떄문에 굉장히 많은 변수를 생각하면서

골치아파지는 경우가 많다.

하지만 위처럼 스케일업 방법을 사용해서 그냥 명확하게만 구분해주는 접근도 쓸 수 있도록 정리를 했다