알고리즘/99Club
99클럽 코테 스터디 32일차 TIL + 아이템 줍기 (BFS)
dami97
2024. 8. 22. 23:22
반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 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 탐색을 하면 경계선의 정확한 경로를 따라가야 하지만, 단일 크기로 테두리를 표현하면 경계선이 정확하게 표시되지 않을 수 있습니다. 따라서, 크기를 두 배로 확장하여 경계선이 명확히 표시되도록 합니다.
이렇게 하면 경계선이 명확하게 구분되어 탐색 과정에서 혼동이 없게 됩니다.
- 지형 그리기
- 직사각형의 좌표를 사용하여 지도에 경계를 그리고, 지도의 크기를 두 배로 확장하여 경계선을 명확하게 구분합니다.
- 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로 표시되고, 내부는 2로 표시됩니다. 이로 인해 경계와 내부를 명확히 구분할 수 있습니다.
- 직사각형의 좌표를 기반으로 지도를 그릴 때, 지도의 크기를 두 배로 확장하여 경계선을 명확히 표시합니다.
- BFS로 최단 경로 탐색
- BFS(너비 우선 탐색)를 사용하여 캐릭터의 초기 위치에서 시작하여 아이템 위치까지의 최단 경로를 탐색합니다.
- 모든 경로를 같은 우선순위로 탐색하므로 가장 짧은 경로를 보장할 수 있습니다.
- visited 배열을 사용하여 이미 방문한 위치를 다시 방문하지 않도록 관리합니다.
- 결과 반환
- BFS 탐색을 통해 아이템 위치에 도달한 경우, 이동한 거리를 반환합니다.
- 거리는 지도를 2배로 확장했기 때문에, 최종 결과는 distance / 2로 계산하여 반환합니다.
마무리하며
- 직사각형의 경계를 명확히 표시하기 위해 지도의 크기를 두 배로 확장하는 방식으로 문제를 해결했습니다.