- DFS와 BFS를 이용한 풀이
문제 요약
'X'는 바다, 숫자는 섬으로 이뤄진 문자열 배열이 주어진다. 숫자는 1~9까지로 이뤄지며, 식량을 의미한다. 숫자가 상,하,좌,우로 연결된 섬은 하나의 섬이며, 이 때 각 섬마다 최대 며칠씩 머물 수 있는지 배열에 오름차순으로 담아 반환하라
[ 예시 ]
| maps | result |
|---|---|
| ["X591X","X1X5X","X231X", "1XXX1" | [1, 1, 27] |
| ["XXX","XXX","XXX"] | [-1] |
[ 제약 조건 ]
- 3≤
maps[i]의 길이≤100 - 지도는 직사각형이다.
- 1≤
maps[i]의 요소≤9
[ 프로그래머스 ]
풀이
- 전체 배열을 모두 탐색해야하기에
BFS(Brute Force)사용 - 최대 머물 수 있는 기간은 가변적이기에
ArrayList에 결과값 저장
(1) 주어진 maps를 편리하게 이용하기 위해 이중 배열로 초기화
- 이 때,
'X'는-1로 초기화한다.
(2) 이중 for문을 통해 칸 전체를 탐색한다.
- 이때, 바다가 아니면서 방문한 적이 없는 칸은
-1이 아님으로BFS함수로 해당x,y값을 보낸다.
(3) Queue를 선언하여, 다음으로 이동할 칸의 x, y값을 넣는다.
(4) 섬의 전체 식량을 계산하기 위해 sum을 선언하고, 연결된 다른 칸에 방문할 때마다 해당 칸의 숫자를 sum에 누적합한다.
(5) 이미 방문한 섬은 -1로 설정하여, 다시 방문하지 않도록 설정한다.
(6) 하나의 섬에 연결된 모든 칸의 식량이 최종 sum에 저장되며, 해당 값을 반환한다.
(7) 반환 받은 sum을 ArrayList에 넣고, 만일 ArrayList의 길이가 0이라면 방문 가능한 섬이 없음을 의미하기에 -1을 넣는다.
Code
import java.util.*;
class Solution {
static int N, M;
static int[][] board;
public ArrayList<Integer> solution(String[] maps) {
int[] answer = {};
N = maps.length;
M = maps[0].length();
board = new int[N][M];
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
char c = maps[i].charAt(j);
if (c == 'X') board[i][j] = -1;
else board[i][j] = c -'0';
}
}
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if (board[i][j] != -1)
list.add(bfs(i,j));
}
}
Collections.sort(list);
if (list.size() == 0)
list.add(-1);
return list;
}
private static int bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x,y});
int sum = board[x][y];
board[x][y]=-1;
int[] mx = {0,0,1,-1};
int[] my = {1,-1,0,0};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for(int i=0;i<4;i++) {
int nx = cur[0] + mx[i];
int ny = cur[1] + my[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (board[nx][ny] == -1)
continue;
queue.add(new int[]{nx,ny});
sum += board[nx][ny];
board[nx][ny] = -1;
}
}
return sum;
}
}시도
1) DFS와 누적합
DFS를 이용하여 board의 각 구간에 누적합을 하는 방식을 시도했지만, 뭔가 답은 나오는데 구체적으로 잡히진 않았다. 최종 결과값만 ArrayList에 넣을지 같은 그런 감들. 아직 익숙하지 않는 듯 하여 BFS로 방식을 변경하였다.
※ 풀었다!
import java.util.*;
class Solution {
static boolean[][] visited;
static int[][] board;
static int N,M;
static int[] mx = {0,0,1,-1};
static int[] my = {1,-1,0,0};
static ArrayList<Integer> list;
public ArrayList<Integer> solution(String[] maps) {
int[] answer = {};
N = maps.length;
M = maps[0].length();
board = new int[N][M];
list = new ArrayList<>();
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
char c = maps[i].charAt(j);
if (c == 'X') board[i][j] = -1;
else board[i][j] = c -'0';
}
}
int result = 0;
for(int i=0;i<N;i++) {
for (int j=0;j<M;j++) {
if (board[i][j] != -1) {
result = dfs(i,j, result);
list.add(result);
result = 0;
}
}
}
if (list.size() == 0)
list.add(-1);
Collections.sort(list);
return list;
}
private static int dfs(int x, int y, int result) {
result += board[x][y];
board[x][y] = -1;
for(int i=0;i<4;i++) {
int nx = x + mx[i];
int ny = y + my[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (board[nx][ny]==-1)
continue;
result = dfs(nx,ny,result);
}
return result;
}
}
2) BFS
DFS보다는 BFS가 재귀 호출을 안 해서 머리 속으로 쉽게 시뮬레이션되었다. 암튼 잘 돌아간다. :>
느낀점
이번 문제로 내가 BFS보다는 DFS 풀이에 취약함을 알았다. 해결 방안은 많이 풀어 보는 것 외는 없다. 킵고잉~
이 또한 지나가리라