🎯문제
메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.
지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.
제한사항
- 3 ≤ maps의 길이 ≤ 100
- 3 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
- 지도는 직사각형 형태입니다.
입출력 예
| maps | result |
|---|---|
| ["X591X","X1X5X","X231X", "1XXX1"] | [1, 1, 27] |
| ["XXX","XXX","XXX"] | [-1] |
입출력 예 설명
입출력 예 #1
위 문자열은 다음과 같은 지도를 나타냅니다.
연결된 땅들의 값을 합치면 다음과 같으며
이를 오름차순으로 정렬하면 [1, 1, 27]이 됩니다.
입출력 예 #2
위 문자열은 다음과 같은 지도를 나타냅니다.
섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.
✏️풀이
코드
import java.util.*;
class Solution {
// 상하좌우로 움직이기 위해 필요한 x, y배열
int[] dx = {1, 0, -1, 0};
int[] dy = {0, 1, 0, -1};
// 무인도의 지도와 방문여부를 저장할 배열
char[][] map;
boolean[][] visit;
// bfs 탐색
public int bfs(int x, int y) {
// 묵을 수 있는 총 날짜
int sum = 0;
// 방문여부 바꿔줌
visit[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] {x, y});
// 큐가 비어있을 때까지 반복
while(!q.isEmpty()) {
// 큐에 있는 값을 하나 가져옴
int[] temp = q.poll();
int nx = temp[0];
int ny = temp[1];
// 묵을 수 있는 날을 더해줌
sum += map[nx][ny] - '0';
// 상하좌우로 움직여줌
for(int i = 0; i < 4; i++) {
int mx = nx + dx[i];
int my = ny + dy[i];
// 지도 범위에 벗어나면 continue
if(mx < 0 || my < 0 || mx >= map.length || my >= map[0].length) {
continue;
}
// 방문한 적 없으며 갈 수 있는 곳이라면
if(!visit[mx][my] && map[mx][my] != 'X') {
// 방문여부 바꿔주고 큐에 값을 저장
visit[mx][my] = true;
q.offer(new int[] {mx, my});
}
}
}
// 나온 총합을 반환
return sum;
}
public int[] solution(String[] maps) {
map = new char[maps.length][maps[0].length()];
visit = new boolean[maps.length][maps[0].length()];
for(int i = 0; i < maps.length; i++) {
map[i] = maps[i].toCharArray();
}
// 탐색된 값을 저장할 배열
ArrayList<Integer> answer = new ArrayList<>();
// 지도 탐색을 시작
for(int i = 0; i < maps.length; i++) {
for(int j = 0; j < maps[0].length(); j++) {
if(!visit[i][j] && map[i][j] != 'X') {
answer.add(bfs(i, j));
}
}
}
// 배열에 값이 없다면 -1을 넣어줌
if(answer.size() == 0){
answer.add(-1);
}
// 오름차순으로 정렬
Collections.sort(answer);
// int[] 형으로 바꿔서 반환
return answer.stream().mapToInt(i -> i).toArray();
}
}설명
bfs 탐색을 사용해서 진행하였다.
현재 위치에서 상하좌우로 움직이기 위해서 필요한 x, y의 값들을 각각 배열에 저장해서 dx, dy 배열을 만들어준다. 그리고 지도를 2차원 배열로 저장하기 위한 배열과 해당 위치의 방문여부를 저장하기 위한 배열을 선언해준다.
bfs 탐색 메서드는 x, y를 매개변수로 받는다. x, y는 2차원 배열의 인덱스이며 map[x][y]부터 탐색을 진행한다는 뜻이다. 해당 위치부터 연관된 모든 곳을 탐색한 뒤 반환하므로 탐색하면서 묵을 수 있는 날짜를 저장할 sum 변수를 0으로 초기화해준 뒤 방문여부를 true로 바꿔준다.
bfs의 특징은 큐를 사용한다는 것이다. 큐에 매개변수로 가져온 값을 넣어주고 while문을 반복한다. while문의 조건은 큐가 비어있지 않다면 계속 반복을 진행하는 것이고, while문 안에서는 큐의 맨 앞 값을 가져와서 sum에 묵을 날짜를 더해준다. 이후 for문을 통해서 해당 위치에서 위쪽, 아래쪽, 왼쪽, 오른쪽을 탐색해준다. 지도의 범위에 벗어나지 않고 방문한 적이 없으며 갈 수 있는 곳이라면 큐에 값을 넣어준다.
정리하자면 한 곳을 탐색하고 그 위치를 기준으로 상하좌우를 탐색해서 갈 수 있는 모든 곳을 탐색한 뒤 저장한다. 이후 다시 큐에서 그 값을 꺼내와서 해당 위치를 기준으로 상하좌우를 다시 탐색하는 것이다. 이 특징 때문에 dfs는 깊이 우선 탐색이지만 bfs 너비 우선 탐색이라고 불린다.
map, visit 배열을 생성해준 뒤에 map 배열에 값을 넣어준다.
ArrayList를 사용해서 bfs 탐색을 진행한 뒤 나온 값들을 저장해준다. 나올 수 있는 값이 몇개인지 모르기 때문에 동적배열을 사용하였다.
for문을 통해 지도 탐색을 시작하고 탐색이 끝난 값은 answer 배열에 저장이 된다.
모든 반복문이 끝난 뒤에 배열에 값이 없다면 갈 수 있는 곳이 없다는 뜻이므로 배열에 -1을 넣어준다. 이후 오름차순 정렬을 통해 값을 정렬해주고 반환형식에 맞게 int[]형 배열로 바꾸어서 반환해준다면 문제를 해결할 수 있다!
💡느낀 점
bfs 탐색을 사용해서 문제를 풀었는데, 최근 dfs 탐색만 사용해서 풀다보니 맨 처음 bfs 탐색을 사용해야겠다는 생각은 했으나 코드를 짤 수 없었다.. 그래서 bfs 탐색을 다시 공부하면서 문제를 풀다보니 이전에 사용했던 기억들이 새록새록 떠오르면서 문제를 해결할 수 있었다. 이번 문제는 bfs 탐색만 잘 알고 있다면 수월하게 풀 수 있는 문제였던 것 같다!
링크
