💡 문제
아이템 줍기 (https://school.programmers.co.kr/learn/courses/30/lessons/87694)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
이 문제를 해결하려면 주로 그래프 탐색 알고리즘과 2차원 배열을 다루는 방법을 이해해야 합니다. 아래는 문제를 푸는 데 필요한 주요 개념들입니다.
1. BFS (Breadth-First Search)
BFS는 그래프 또는 트리의 탐색 알고리즘 중 하나로, 너비 우선 탐색이라고도 합니다. BFS는 특정 노드에서 시작하여 인접한 모든 노드를 방문한 후, 방문한 노드를 기준으로 다시 인접한 노드들을 방문하는 방식으로 진행됩니다. BFS의 주요 특징은 다음과 같습니다:
- 최단 경로 탐색: BFS는 최단 경로 문제를 해결하는 데 적합합니다.
- 큐 사용: BFS는 FIFO(First In, First Out) 방식의 큐를 사용하여 탐색합니다.
BFS 알고리즘의 동작 과정:
- 탐색을 시작할 노드를 큐에 삽입하고, 해당 노드를 방문 표시합니다.
- 큐에서 노드를 꺼내 해당 노드와 인접한 모든 노드를 확인합니다.
- 인접한 노드 중 아직 방문하지 않은 노드를 큐에 삽입하고 방문 표시합니다.
- 큐가 빌 때까지 2번과 3번 과정을 반복합니다.
2. 2차원 배열
2차원 배열은 행과 열로 구성된 데이터 구조로, 주로 매트릭스 형태로 데이터를 저장하고 처리할 때 사용됩니다. 이 문제에서는 직사각형 지형을 나타내기 위해 2차원 배열을 사용합니다.
2차원 배열의 주요 연산:
- 초기화: 배열을 특정 값으로 초기화합니다.
- 접근: 배열의 특정 위치에 접근하여 값을 읽거나 수정합니다.
- 탐색: 배열의 모든 요소를 순회하여 조건에 맞는 값을 찾습니다.
3. 좌표 평면과 확장된 좌표계
문제에서 직사각형의 좌표는 겹치는 부분이 없고, 좌표가 소수점 없이 정수로 주어집니다. 좌표의 범위를 확장하여 처리하는 이유는 더 정밀하게 테두리를 설정하기 위함입니다.
좌표 평면 확장:
- 2배 확장: 좌표값을 2배로 확장하여 좌표 사이의 공간을 더 정밀하게 표현합니다.
- 이점: 겹치는 부분이나 테두리를 더 정확하게 구분할 수 있습니다.
4. 그래프와 인접 행렬
그래프는 노드와 그 노드를 연결하는 간선으로 이루어진 자료 구조입니다. 이 문제에서는 지형의 테두리를 그래프의 노드로 보고, 각 노드를 인접한 노드와 연결하여 탐색합니다.
인접 행렬:
- 그래프의 노드 간 연결 관계를 2차원 배열로 표현합니다.
- 배열의 요소는 두 노드 간의 간선 유무를 나타냅니다.
🤓 문제 풀이
🔨 문제 설명
다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.
지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.
단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.
즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.
다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.
한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.ㅍ
이 문제를 해결하기 위해서는 BFS (너비 우선 탐색)를 사용하는 것이 적절합니다. BFS는 최단 경로를 찾기 위한 탐색 알고리즘으로, 캐릭터가 아이템을 줍기 위해 다각형 테두리를 따라 이동해야 하는 가장 짧은 거리를 찾기에 적합합니다. BFS는 단계별로 모든 경로를 탐색하며, 가장 먼저 목표 지점에 도달하는 경로가 최단 경로가 됩니다.
🔨 문제 접근 방법
- 격자 크기 확장: 문제의 좌표값이 1부터 50까지의 자연수로 주어지므로, 좌표값을 2배로 확장하여 정밀도를 높입니다. 이는 좌표가 겹치거나 간섭되는 문제를 피하기 위해서입니다.
- 테두리 추출: 주어진 직사각형들의 테두리를 추출합니다. 이는 캐릭터가 이동할 수 있는 경로를 명확히 하기 위함입니다.
- BFS 초기화: 큐를 사용하여 BFS를 수행합니다. 시작 지점과 초기 거리를 큐에 넣습니다.
- BFS 탐색: 큐에서 현재 위치를 꺼내어 가능한 모든 이동을 시도하며, 목표 위치에 도달하면 이동 거리를 반환합니다.
🔨 문제 풀이 과정
- 지형 설정:
- 입력으로 주어진 직사각형들을 바탕으로 지형을 설정합니다. 좌표의 범위를 2배로 확장하여 처리했습니다. 이는 더 정밀한 테두리 설정을 위함입니다.
- 내부 영역 제거 (테두리 설정):
- 직사각형의 테두리를 따라 이동할 수 있도록 경로를 설정합니다. 직사각형 내부를 false로 설정하여 테두리만 남깁니다. 이렇게 하면 캐릭터가 다각형의 외곽을 따라 이동할 수 있습니다.
- BFS 탐색:
- 시작 지점에서 BFS를 사용하여 목표 지점까지 최단 거리를 찾습니다. BFS는 FIFO(First In, First Out) 방식의 큐를 사용하여 현재 위치에서 네 방향으로 이동하면서 탐색합니다.
- 큐를 사용하여 현재 위치에서 이동할 수 있는 모든 경로를 탐색하고, 목표 위치에 도달하면 그 거리를 반환합니다.
🔨 BFS 선택
BFS는 모든 가능한 경로를 동일한 깊이로 탐색하며, 최단 경로를 보장합니다. 이 문제에서는 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 찾아야 하므로, BFS가 적합합니다. 또한, BFS는 큐를 사용하여 구현하기 쉽고, 탐색 과정에서 불필요한 경로를 제거할 수 있습니다.
이 문제의 BFS 알고리즘은 최악의 경우에도 효율적으로 동작하도록 설계되었습니다. 이는 문제의 제약 조건 내에서 충분히 효율적인 시간과 공간 복잡도를 가지며, 최단 경로를 찾는 데 적합합니다.
🔨 구현코드
import java.util.*;
class Solution {
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
int MAX = 102; // 좌표의 최대값을 2배로 확장하여 더 큰 맵 생성
boolean[][] map = new boolean[MAX][MAX];
// 모든 직사각형의 영역을 true로 설정
for (int[] rect : rectangle) {
int x1 = rect[0] * 2;
int y1 = rect[1] * 2;
int x2 = rect[2] * 2;
int y2 = rect[3] * 2;
// 직사각형의 영역을 true로 설정
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
map[i][j] = true;
}
}
}
// 내부 영역을 false로 설정하여 테두리만 남김
for (int[] rect : rectangle) {
int x1 = rect[0] * 2 + 1;
int y1 = rect[1] * 2 + 1;
int x2 = rect[2] * 2 - 1;
int y2 = rect[3] * 2 - 1;
// 직사각형 내부 영역을 false로 설정
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
map[i][j] = false;
}
}
}
// 캐릭터와 아이템의 시작 위치를 2배로 확장
int startX = characterX * 2;
int startY = characterY * 2;
int endX = itemX * 2;
int endY = itemY * 2;
// BFS를 위한 큐와 방문 배열 초기화
Queue<int[]> queue = new LinkedList<>();
// - 각 좌표를 방문했는지 기록하기 위해 방문 배열을 초기화
boolean[][] visited = new boolean[MAX][MAX];
// 시작 위치 큐 삽입 시작 위치를 큐에 삽입하고 방문 표시
queue.offer(new int[]{startX, startY, 0});
visited[startX][startY] = true;
// BFS 탐색을 위한 방향 배열
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// BFS 탐색 시작
// 큐에서 노드를 꺼내 네 방향으로 이동하며 탐색합니다. 유효한 좌표 내에서 이동 가능하고 방문하지 않은 경우에만 큐에 삽입합니다.
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
int dist = current[2];
// 아이템 위치에 도달하면 거리 반환
if (x == endX && y == endY) {
return dist / 2; // 확장된 거리이므로 2로 나누어 원래 거리로 변환
}
// 현재 위치에서 네 방향으로 이동
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 유효한 좌표 내에서 이동 가능하고 방문하지 않은 경우
if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX && map[nx][ny] && !visited[nx][ny]) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny, dist + 1});
}
}
}
return 0; // 목표 지점에 도달하지 못한 경우
}
}📚 풀이 보완
코드 설명
- 테두리 설정: 먼저 모든 직사각형 영역을 map에 true로 설정합니다.
- 내부 영역 제거: 각 직사각형의 내부 영역을 false로 설정하여 테두리만 남깁니다.
- BFS 탐색: 시작 지점에서 BFS를 시작하여 테두리를 따라 이동하며, 목표 지점에 도달하면 그 거리를 반환합니다.
처음 구현한 코드에서 발생한 틀린 부분
- 내부 영역과 테두리 설정 오류:
- 내부 영역과 테두리 설정이 불분명하여 불필요한 경로 탐색을 하였습니다.
- map 배열에 직사각형 내부 영역까지 포함되어 경로 탐색 시 문제가 발생했습니다.
두 번째로 수정한 코드에서 발생한 틀린 부분
- 테두리와 내부 영역 처리:
- 두 번째 수정에서도 여전히 테두리 설정이 명확하지 않았습니다.
- 내부 영역을 명확히 제거하지 못해 여전히 잘못된 경로가 포함되었습니다.
마지막 코드에서 문제를 풀 수 있었던 해결점
- 정확한 테두리 설정:
- 모든 직사각형의 내부를 false로 설정하여 정확히 테두리만 남겼습니다.
- 직사각형의 모든 좌표를 true로 설정한 후, 내부 좌표를 false로 변경하여 정확한 테두리만 남기는 방법을 사용했습니다.
- BFS 탐색:
- 정확한 테두리를 따라 BFS를 실행하여 올바른 경로를 탐색했습니다.
요약
- 첫 번째 구현: 내부와 테두리의 구분이 명확하지 않아 잘못된 경로 탐색.
- 두 번째 구현: 테두리와 내부의 구분을 시도했지만 여전히 불완전.
- 마지막 구현: 모든 직사각형을 true로 설정한 후, 내부를 false로 설정하여 정확한 테두리만 남김. BFS로 올바른 경로 탐색하여 문제 해결.
📍 Plus+
공간 복잡도
- 큐(Queue): BFS는 탐색 과정에서 방문할 노드를 저장하기 위해 큐를 사용합니다. 최악의 경우, 큐에는 그래프의 모든 노드가 저장될 수 있습니다.
- 방문 배열: 각 노드의 방문 여부를 저장하기 위해 별도의 배열이 필요합니다.
주어진 문제에서는 최대 50 x 50 크기의 좌표 평면을 2배 확장한 102 x 102 크기로 사용합니다. 방문 배열과 맵 배열 모두 이러한 크기를 가지므로, 각 배열의 공간 복잡도는 O(N^2)입니다. 따라서 전체 공간 복잡도는 O(N^2)입니다.
시간복잡도
- 노드 방문: BFS는 모든 노드를 한 번씩 방문합니다.
- 간선 탐색: 각 노드에서 인접한 모든 간선을 탐색합니다.
주어진 문제에서는 최대 50 x 50 크기의 좌표 평면을 2배 확장한 102 x 102 크기로 사용합니다. 확장된 좌표 평면 내에서 BFS를 수행할 때, 모든 가능한 좌표를 방문하고, 각 좌표에서 최대 4개의 인접한 좌표를 탐색합니다. 최악의 경우, 모든 좌표를 방문하고, 모든 간선을 탐색해야 하므로 시간 복잡도는 O(N^2)입니다.
요약
- 공간 복잡도 : O(N^2)
- 시간 복잡도 : O(N^2)
다른 알고리즘 풀이법
해당 문제는 주어진 제약 조건(직사각형 지형의 테두리만을 따라 이동해야 함)과 최단 경로를 찾는다는 점에서 BFS가 가장 적합한 알고리즘입니다. 그러나 다른 알고리즘으로도 문제를 해결할 수는 있습니다.
1. DFS (Depth-First Search)
DFS는 그래프 탐색에서 깊이를 우선으로 하는 탐색 알고리즘입니다. DFS를 사용하여 문제를 풀 수는 있지만, 최단 경로를 찾기 위해서는 모든 가능한 경로를 탐색해야 하므로 비효율적입니다. DFS는 주로 경로가 존재하는지 여부를 확인하는 데 유용합니다.
DFS를 사용하여 모든 경로를 탐색하고, 가장 짧은 경로를 기록할 수 있습니다. 그러나 이 경우 탐색해야 할 경로가 많아질 수 있으므로, 시간 복잡도가 BFS보다 높아질 수 있습니다.
2. Dijkstra's Algorithm
Dijkstra 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 사용됩니다. 이 문제는 무가중치 그래프이므로, Dijkstra 알고리즘을 사용할 수 있지만, BFS가 더 간단하고 효율적입니다.
3. A* Algorithm
A* 알고리즘은 휴리스틱을 사용하여 경로 탐색을 최적화하는 알고리즘입니다. 이 문제에 대해 A* 알고리즘을 사용할 수 있지만, BFS가 최단 경로를 찾는 데 이미 효율적이므로 필요하지 않습니다.
DFS로 해결하는 코드 예시
DFS를 사용하여 문제를 해결하는 코드를 작성해 보겠습니다. 최단 경로를 찾기 위해 모든 경로를 탐색해야 하므로, 백트래킹(backtracking)을 사용하여 구현합니다.
import java.util.*;
class Solution {
private int minDistance = Integer.MAX_VALUE;
private int MAX = 102;
private boolean[][] map;
private boolean[][] visited;
// DFS 탐색을 위한 방향 배열
private int[] dx = {-1, 1, 0, 0};
private int[] dy = {0, 0, -1, 1};
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
map = new boolean[MAX][MAX];
visited = new boolean[MAX][MAX];
// 모든 직사각형의 영역을 true로 설정
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++) {
map[i][j] = true;
}
}
}
// 내부 영역을 false로 설정하여 테두리만 남김
for (int[] rect : rectangle) {
int x1 = rect[0] * 2 + 1;
int y1 = rect[1] * 2 + 1;
int x2 = rect[2] * 2 - 1;
int y2 = rect[3] * 2 - 1;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
map[i][j] = false;
}
}
}
// 캐릭터와 아이템의 시작 위치를 2배로 확장
int startX = characterX * 2;
int startY = characterY * 2;
int endX = itemX * 2;
int endY = itemY * 2;
// DFS 탐색 시작
dfs(startX, startY, endX, endY, 0);
return minDistance / 2; // 확장된 거리이므로 2로 나누어 원래 거리로 변환
}
private void dfs(int x, int y, int endX, int endY, int dist) {
// 아이템 위치에 도달하면 최소 거리 갱신
if (x == endX && y == endY) {
minDistance = Math.min(minDistance, dist);
return;
}
// 방문 처리
visited[x][y] = true;
// 현재 위치에서 네 방향으로 이동
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 유효한 좌표 내에서 이동 가능하고 방문하지 않은 경우
if (nx >= 0 && ny >= 0 && nx < MAX && ny < MAX && map[nx][ny] && !visited[nx][ny]) {
dfs(nx, ny, endX, endY, dist + 1);
}
}
// 백트래킹: 방문 해제
visited[x][y] = false;
}
}요약
- BFS: 가장 적합한 알고리즘으로, 최단 경로를 효율적으로 찾을 수 있습니다. 시간 복잡도와 공간 복잡도 모두 O(N^2)입니다.
- DFS: 모든 경로를 탐색하여 최단 경로를 찾을 수 있지만, 비효율적입니다. 시간 복잡도가 높아질 수 있습니다.
- Dijkstra, A: 이 문제는 무가중치 그래프이므로 BFS가 이미 최적화된 선택입니다. 가중치가 있다면 고려해볼 수 있습니다.
따라서, 주어진 문제에서는 BFS가 최적의 선택입니다. 다른 알고리즘도 사용 가능하지만, 효율성 측면에서는 BFS를 사용하는 것이 가장 좋습니다.
'Algorithm > 코딩테스트' 카테고리의 다른 글
| [프로그래머스][JAVA] 43162. 네트워크 (1) | 2024.06.09 |
|---|---|
| [프로그래머스][JAVA] 43163. 단어변환 (1) | 2024.06.09 |
| [프로그래머스][JAVA] 43164. 여행경로 (1) | 2024.06.09 |
| [프로그래머스][JAVA] 84512. 모음사전 (0) | 2024.06.05 |
| [프로그래머스][JAVA] 84021. 퍼즐조각채우기 (0) | 2024.06.01 |