프로그래머스 | Level 2 | 무인도 여행
Programmers | Level 2 | 무인도 여행
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Breadth-First Search
Description
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.
지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.
Constraints
- 3 ≤
maps의 길이 ≤ 100- 3 ≤
maps[i]의 길이 ≤ 100 maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.- 지도는 직사각형 형태입니다.
- 3 ≤
Examples
| maps | result |
|---|---|
["X591X","X1X5X","X231X","1XXX1"] | [1, 1, 27] |
["XXX","XXX","XXX"] | [-1] |
Solutions
Code
import java.util.*;
class Solution {
// 상하좌우로 이동하기 위한 델타 배열
private static final int[] dx = {0, 1, 0, -1}; // x 방향
private static final int[] dy = {1, 0, -1, 0}; // y 방향
public int[] solution(String[] maps) {
int rows = maps.length; // 지도 행의 수
int cols = maps[0].length(); // 지도 열의 수
int[][] grid = new int[rows][cols]; // 각 칸의 숫자를 저장할 배열
boolean[][] marked = new boolean[rows][cols]; // 방문 여부를 기록할 배열
// 지도 초기화 및 방문 체크 배열 설정
for (int i = 0; i < rows; i++) {
String[] spots = maps[i].split(""); // 각 행을 문자열 배열로 변환
for (int j = 0; j < cols; j++) {
if (spots[j].equals("X")) { // 'X'인 경우, 바다로 처리하여 방문 불가 상태로 설정
marked[i][j] = true;
} else {
grid[i][j] = Integer.parseInt(spots[j]); // 숫자는 무인도를 나타내므로 정수로 변환해 저장
}
}
}
// 무인도에서 머무를 수 있는 일수를 저장할 리스트
List<Integer> days = new ArrayList<>();
// 모든 칸을 순차적으로 확인하며 BFS를 통해 무인도를 탐색
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (marked[i][j]) continue; // 이미 방문한 칸은 건너뛰기
int day = bfs(grid, marked, rows, cols, i, j); // BFS를 통해 무인도 탐색 및 일수 계산
days.add(day); // 해당 무인도에서 머무를 수 있는 일수를 리스트에 추가
}
}
// 탐색한 무인도가 없으면 -1을 반환, 그렇지 않으면 오름차순으로 정렬하여 결과 반환
return days.isEmpty()
? new int[]{-1}
: days.stream().mapToInt(Integer::valueOf).sorted().toArray();
}
// BFS를 통한 무인도 탐색
private int bfs(int[][] grid, boolean[][] marked, int rows, int cols, int sx, int sy) {
Deque<int[]> queue = new ArrayDeque<>(); // BFS에 사용할 큐 생성
queue.offer(new int[]{sx, sy}); // 시작점을 큐에 추가
marked[sx][sy] = true; // 시작점을 방문 처리
int total = 0; // 무인도에서 얻을 수 있는 총 식량을 저장할 변수
while (!queue.isEmpty()) {
int[] current = queue.poll(); // 큐에서 현재 위치 꺼내기
int cx = current[0]; // 현재 x 좌표
int cy = current[1]; // 현재 y 좌표
total += grid[cx][cy]; // 현재 칸의 식량을 총합에 더하기
// 상하좌우로 이동하여 연결된 칸 탐색
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i]; // 새로운 x 좌표
int ny = cy + dy[i]; // 새로운 y 좌표
// 범위 내에 있고 아직 방문하지 않은 칸이면 큐에 추가
if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && !marked[nx][ny]) {
queue.offer(new int[]{nx, ny}); // 새로운 좌표 큐에 추가
marked[nx][ny] = true; // 방문 처리
}
}
}
return total; // 무인도에서 얻은 총 식량 반환
}
}
Approach
이 문제는 지도에서 무인도를 탐색하여, 각각의 무인도에서 머무를 수 있는 최대 일수를 구하고, 이를 오름차순으로 정렬해 반환하는 문제입니다. 무인도를 탐색하는 과정에서 BFS(너비 우선 탐색)을 이용하여 상하좌우로 연결된 무인도를 하나의 덩어리로 묶고, 그 안의 값을 합산하여 머무를 수 있는 일수를 구하는 방식입니다.
1. 문제 분석
무인도를 찾고, 각 무인도에서 머무를 수 있는 최대 일수를 계산하는 문제입니다. 이때 상하좌우로 연결된 땅들이 하나의 무인도를 이루며, 무인도는 독립적으로 존재합니다. 따라서 이 문제는 단순히 지도를 보고 섬을 식별하는 것에서 끝나지 않고, 탐색을 통해 각 무인도의 범위를 명확하게 구분하고, 각 무인도의 자원을 최대한 활용할 수 있는지 파악하는 것이 핵심입니다.
이 과정은 기본적으로 그래프 탐색의 개념을 이용해 해결할 수 있습니다. 그래프 탐색에서는 한 점에서 출발해 연결된 다른 점들을 찾고, 이 과정에서 같은 그룹으로 묶이는 모든 점들을 하나의 연결 요소로 파악합니다. 여기서 각 칸은 그래프의 노드로 볼 수 있으며, 상하좌우로 이동할 수 있는 경로는 간선에 해당합니다. 이 문제에서 우리는 무인도를 이루는 땅들을 하나의 연결 요소로 보고, 해당 요소에 속한 칸들의 값을 더해 최대 머무를 수 있는 일수를 계산하게 됩니다.
무인도를 찾는 방식으로는 깊이 우선 탐색 또는 너비 우선 탐색을 사용할 수 있으며, 여기서는 넓게 퍼진 섬을 효율적으로 탐색하기 위해 BFS를 사용하는 것이 더 적합할 것 같습니다. 상하좌우로 연결된 무인도를 하나로 묶는 과정에서 중요한 점은, 이미 방문한 칸을 다시 탐색하지 않도록 방문 여부를 관리하는 것입니다. 탐색이 완료되면 해당 섬에서 머무를 수 있는 일수를 계산해 리스트에 기록하고, 모든 섬을 탐색한 후 결과를 오름차순으로 정렬해 반환하는 것이 목표입니다.
2. 접근 방식
문제 해결을 위해 먼저 지도를 초기화하고, 각 칸의 상태를 확인하여 탐색을 시작합니다. BFS를 사용해 상하좌우로 연결된 무인도를 하나의 그룹으로 묶고, 그 그룹의 식량 총합을 계산합니다. 탐색이 끝난 후, 각 무인도의 최대 머무를 수 있는 일수를 리스트에 기록하고, 모든 탐색이 완료되면 결과를 오름차순으로 정렬해 반환합니다:
- 지도 초기화 및 데이터 변환: 주어진 문자열 배열
maps에서 각 칸을 분리하여, 바다와 땅을 구분합니다. 'X'는 바다이므로 방문할 수 없도록 별도의 배열에 방문 여부를 표시하고, 숫자는 무인도를 나타내므로 정수형 배열로 변환해 저장합니다. - 탐색 준비: 각 칸을 순차적으로 확인하며, 아직 방문하지 않은 땅을 발견할 경우, 그 위치에서 BFS 탐색을 시작합니다. 처음 발견한 땅의 좌표를 큐에 추가하고, 상하좌우로 연결된 칸들을 차례대로 탐색합니다.
- BFS 탐색: BFS는 큐에서 좌표를 하나씩 꺼내 상하좌우로 이동하며 연결된 땅을 찾아냅니다. 큐에서 꺼낸 칸의 값을 식량 총합에 더하며, 그 칸이 방문되었음을 기록해 다시 탐색하지 않도록 합니다. 이를 통해 하나의 무인도를 탐색하고, 해당 무인도의 총 식량을 계산합니다.
- 일수 계산: 하나의 무인도에 대한 BFS 탐색이 완료되면, 해당 무인도에서 얻을 수 있는 총 식량을 바탕으로 머무를 수 있는 일수를 기록합니다. 이러한 값은 리스트에 저장됩니다.
- 결과 정리: 모든 탐색이 완료되면, 각 무인도에서 머무를 수 있는 일수들이 저장된 리스트를 오름차순으로 정렬해 반환합니다. 만약 탐색 가능한 무인도가 없다면,
-1을 반환하여 이를 처리합니다.
3. 지도 초기화 및 BFS 탐색 준비
먼저 무인도를 탐색하기 위한 준비를 해야 합니다. 식량을 용이하게 추적하기 위해 숫자형으로 된 무인도 배열과 방문 여부를 기록할 배열을 초기화 한 다음 주어진 지도 데이터를 가공합니다. 지도를 순회하면서, 숫자는 무인도 배열에 기록하고, 바다는 접근할 수 없는 영역이므로 방문 배열에 이미 방문한 것으로 표시합니다. 이렇게 각 칸의 상태를 기록하고 나면, 무인도를 탐색할 준비가 완료됩니다.
int rows = maps.length; // 지도 행의 크기 설정
int cols = maps[0].length(); // 지도 열의 크기 설정
int[][] grid = new int[rows][cols]; // 무인도의 숫자를 저장할 배열
boolean[][] marked = new boolean[rows][cols]; // 방문 여부를 기록할 배열
// 지도 초기화 및 탐색 준비
for (int i = 0; i < rows; i++) {
String[] spots = maps[i].split(""); // 지도 배열을 각 칸으로 분리
for (int j = 0; j < cols; j++) {
if (spots[j].equals("X")) {
marked[i][j] = true; // 'X'인 경우 바다로 간주하여 탐색 불가로 설정
} else {
grid[i][j] = Integer.parseInt(points[j]); // 숫자는 무인도를 나타내므로 정수로 변환해 저장
}
}
}
4. BFS를 활용한 무인도 탐색 및 일수 계산
다음은 BFS를 통해 상하좌우로 연결된 무인도를 탐색하고, 각 무인도에서 얻을 수 있는 총 식량을 계산하여 최대 며칠 동안 머무를 수 있는지를 구해야 합니다. 큐 자료구조를 활용하여 각 무인도를 차례로 탐색하며, 한 무인도에 속하는 모든 칸을 방문하면서 그 값을 누적해 계산합니다. 탐색이 완료되면 해당 무인도의 총 식량을 반환하며, 이를 통해 무인도에서 최대 머무를 수 있는 일수를 계산하게 됩니다.
탐색이 시작되면, 아직 방문하지 않은 무인도에서 BFS를 수행합니다. 이때 큐에 시작 좌표를 넣고, 상하좌우로 연결된 모든 칸을 탐색하며 해당 섬의 식량을 합산해 나갑니다. 이때, 좌표가 지도를 벗어나지 않게 범위를 제한해야 하고 방문한 곳을 다시 방문 하지 않도록 적절한 처리가 필요합니다.
private static final int[] dx = {0, 1, 0, -1}; // 상하좌우 x 좌표 이동
private static final int[] dy = {1, 0, -1, 0}; // 상하좌우 y 좌표 이동
private int bfs(
int[][] grid, // 무인도의 숫자를 저장한 배열
boolean[][] marked, // 방문 여부를 기록한 배열
int rows, // 지도의 행 수
int cols, // 지도의 열 수
int sx, // 시작점의 x 좌표
int sy // 시작점의 y 좌표
) {
Deque<int[]> queue = new ArrayDeque<>(); // BFS를 위한 큐 생성
queue.offer(new int[]{sx, sy}); // 시작점 큐에 추가
marked[sx][sy] = true; // 시작점 방문 처리
int total = 0; // 해당 섬의 총 식량을 저장할 변수
while (!queue.isEmpty()) {
int[] current = queue.poll(); // 큐에서 현재 위치 꺼내기
int cx = current[0]; // 현재 x 좌표
int cy = current[1]; // 현재 y 좌표
total += grid[cx][cy]; // 현재 칸의 식량을 총합에 더하기
// 상하좌우로 이동하여 연결된 칸 탐색
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i]; // 새로운 x 좌표
int ny = cy + dy[i]; // 새로운 y 좌표
// 유효한 좌표 범위 내에서 아직 방문하지 않은 칸 탐색
if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && !marked[nx][ny]) {
queue.offer(new int[]{nx, ny}); // 새로운 좌표 큐에 추가
marked[nx][ny] = true; // 방문 처리
}
}
}
return total; // 무인도에서 얻은 총 식량(일수) 반환
}
그래프 탐색 함수가 준비되었다면 이를 활용하여 전체 지도를 순차적으로 탐색합니다. 각 칸을 확인하며, 아직 방문하지 않은 무인도가 발견되면 BFS를 실행해 그 무인도를 탐색합니다. BFS를 통해 상하좌우로 연결된 모든 땅을 탐색하여 무인도의 크기와 해당 섬에서 얻을 수 있는 총 식량을 계산한 뒤, 이를 리스트에 저장하는 방식으로 진행됩니다.
List<Integer> days = new ArrayList<>(); // 각 무인도에서 얻은 일수를 저장할 리스트
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (marked[i][j]) continue; // 이미 방문한 칸은 건너뛰기
int day = bfs(grid, marked, rows, cols, i, j); // BFS로 무인도 탐색
days.add(day); // 탐색한 무인도에서 얻은 일수 리스트에 추가
}
}
이를 통해 지도에서 방문하지 않은 모든 무인도를 차례로 탐색하고, 각 무인도에서 얻을 수 있는 일수를 계산하여 리스트에 저장하게 됩니다.
5. 결과 정렬 및 반환
모든 무인도에 대한 탐색이 완료되면, 각 무인도에서 계산된 일수가 리스트에 저장됩니다. 이 리스트는 각 무인도에서 머무를 수 있는 최대 일수를 담고 있으며, 마지막으로 이 리스트를 오름차순으로 정렬하는 작업이 필요합니다. 만약, 무인도가 하나도 없는 경우에는 리스트가 비어 있게 되므로, 이때는 -1을 반환하여 탐색할 무인도가 없음을 표시합니다.
// 무인도 탐색 결과가 비어있다면 -1을 반환, 그렇지 않다면 오름차순 정렬하여 반환
return days.isEmpty()
? new int[]{-1}
: days.stream().mapToInt(Integer::valueOf).sorted().toArray();
Complexity
- ⏳ TC: O(n * m)
- 💾 SC: O(n * m)
BFS 탐색은 지도의 모든 칸을 한 번씩 방문하므로, 시간 복잡도는 지도 전체 크기에 비례하여 O(n * m)입니다. 여기서 n은 행의 수, m은 열의 수로, 전체 노드 수는 n * m입니다. 각 노드는 상하좌우로 연결된 최대 4개의 인접 노드를 탐색하므로, 각 노드를 방문하는 데 드는 시간이 전체 칸 수에 비례하게 됩니다. 공간 복잡도 역시 방문 여부를 기록하는 배열과 큐를 사용해 각 노드를 저장하므로, 이 또한 O(n * m)에 해당합니다. 결국, 시간과 공간 복잡도 모두 지도의 크기와 비례하여 O(n * m)으로 계산됩니다.
- Algorithm
- BFS