99클럽 코테 스터디 32일차 TIL + 아이템 줍기 (BFS)

 

 

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

 

문제 & 키워드

• 프로그래머스 - 아이템 줍기 (문제 링크)
• BFS (너비 우선 탐색)
• 그래프 탐색

 

 

문제 설명

지형에 여러 개의 직사각형이 겹쳐져 있고, 캐릭터가 이 지형의 테두리를 따라 이동하여 아이템을 주우려고 합니다. 직사각형들의 좌표와 캐릭터의 초기 위치, 아이템의 위치가 주어졌을 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 구하는 문제입니다.

이 문제에서 직사각형은 겹쳐질 수 있으며, 직사각형 내부는 이동할 수 없는 공간으로 처리됩니다. 캐릭터는 직사각형의 테두리를 따라 이동할 수 있습니다.

 

제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
• 캐릭터와 아이템의 좌표는 항상 테두리 위의 한 점입니다.
• 전체 배점의 50%는 직사각형이 1개인 경우입니다.
• 전체 배점의 25%는 직사각형이 2개인 경우입니다.
• 전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.

 

입출력 예

rectangle	characterX	characterY	itemX	itemY	result
[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]]	1	3	7	8	17
[[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]]	9	7	6	1	11
[[1,1,5,7]]	1	1	4	7	9
[[2,1,7,5],[6,4,10,10]]	3	1	7	10	15
[[2,2,5,5],[1,3,6,4],[3,1,4,6]]	1	4	6	3	10

 

---

 

문제 접근

이 문제의 핵심은 지형의 테두리를 정확히 따라가면서 최단 경로를 찾는 것입니다.

여기서 중요한 것은 직사각형 내부와 경계를 정확히 구분하는 것입니다.

만약 크기를 두 배로 확장하지 않으면, 두 직사각형의 경계가 만나는 부분에서 경계와 내부가 명확히 구분되지 않아 경로 탐색에 오류가 생길 수 있습니다.(튀어나온 테두리 부분이 가로 세로 길이가 1일경우)

예를 들어, 두 직사각형이 인접해 있거나 일부 겹쳐 있는 경우, BFS 탐색을 하면 경계선의 정확한 경로를 따라가야 하지만, 단일 크기로 테두리를 표현하면 경계선이 정확하게 표시되지 않을 수 있습니다. 따라서, 크기를 두 배로 확장하여 경계선이 명확히 표시되도록 합니다.

이렇게 하면 경계선이 명확하게 구분되어 탐색 과정에서 혼동이 없게 됩니다.

1. 지형 그리기
   • 직사각형의 좌표를 사용하여 지도에 경계를 그리고, 지도의 크기를 두 배로 확장하여 경계선을 명확하게 구분합니다.
2. BFS 탐색
   • BFS를 통해 캐릭터의 초기 위치에서 시작하여 아이템 위치에 도달하는 최단 경로를 찾습니다. BFS는 모든 경로를 같은 우선순위로 탐색하므로, 최단 경로를 보장할 수 있습니다.

 

 

풀이 - Java 코드

import java.util.*;

public class Solution {

    // 상하좌우 이동을 위한 방향 설정
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] map = new int[102][102];

        // 직사각형을 지도에 2배 크기로 그리기 (확대하여 그리기)
        for (int[] rect : rectangle) {
            int x1 = rect[0] * 2;
            int y1 = rect[1] * 2;
            int x2 = rect[2] * 2;
            int y2 = rect[3] * 2;

            for (int i = x1; i <= x2; i++) {
                for (int j = y1; j <= y2; j++) {
                    if (i == x1 || i == x2 || j == y1 || j == y2) {
                        if (map[i][j] != 2) { // 테두리
                            map[i][j] = 1;
                        }
                    } else {
                        map[i][j] = 2; // 내부 채우기
                    }
                }
            }
        }

        // BFS로 최단 경로 찾기
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[102][102];

        queue.add(new int[]{characterX * 2, characterY * 2, 0});
        visited[characterX * 2][characterY * 2] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int distance = current[2];

            // 아이템 위치에 도달했을 경우
            if (x == itemX * 2 && y == itemY * 2) {
                return distance / 2;
            }

            // 네 방향으로 이동
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < 102 && ny < 102) {
                    if (map[nx][ny] == 1 && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        queue.add(new int[]{nx, ny, distance + 1});
                    }
                }
            }
        }

        return -1;
    }
}

풀이 설명

1. 지형 그리기
   • 직사각형의 좌표를 기반으로 지도를 그릴 때, 지도의 크기를 두 배로 확장하여 경계선을 명확히 표시합니다.
     • 이렇게 하면 직사각형들이 인접하거나 겹치는 경우에도 경계선이 명확하게 구분되므로, 경계선(1)을 따라 이동만 하면 됩니다.
   • 경계선은 1로 표시되고, 내부는 2로 표시됩니다. 이로 인해 경계와 내부를 명확히 구분할 수 있습니다.
2. BFS로 최단 경로 탐색
   • BFS(너비 우선 탐색)를 사용하여 캐릭터의 초기 위치에서 시작하여 아이템 위치까지의 최단 경로를 탐색합니다.
   • 모든 경로를 같은 우선순위로 탐색하므로 가장 짧은 경로를 보장할 수 있습니다.
   • visited 배열을 사용하여 이미 방문한 위치를 다시 방문하지 않도록 관리합니다.
3. 결과 반환
   • BFS 탐색을 통해 아이템 위치에 도달한 경우, 이동한 거리를 반환합니다.
   • 거리는 지도를 2배로 확장했기 때문에, 최종 결과는 distance / 2로 계산하여 반환합니다.

 

---

 

마무리하며

• 직사각형의 경계를 명확히 표시하기 위해 지도의 크기를 두 배로 확장하는 방식으로 문제를 해결했습니다.