[프로그래머스,Java] Level2: 무인도 여행

 

문제분석

 

완전탐색의 국룰과 같은 4방향 탐색 문제다.

 

문제대로 상, 하 ,좌, 우를 탐색해가며  식량을 더해가면되지만,

 

여기서 특수한룰이, 섬이 분리되어있으면  섬마다 식량의 갯수를 구해줘야한다.

 

우선 4방향 완전탐색에서 해야할일은 다음과같다.

 

1. 방문을체크할 boolean[][] -> 방문체크를안하면 무한루프를 돈다.

2. 재귀를 돌릴 재귀메소드 작성.  -> 재귀의 탈출 및 예외조건을 유의해야한다.

3. 추가로 이 문제에서 묻는 섬마다 분리시키는법

 

 

 

우선 분리한 아일랜드의 식량합계를 담는  island 배열과

식량의 합계를 저장할 sum과

방문을 체크하는 visited를 선언했다. visited는 섬의 크기만큼 늘려준다.

 

이제 하나의 섬을 탐색할 스타팅 포인트를 찾을것이다.

포인트가 "X"가 아니면 숫자니, 숫자포인트에서  식량합계를 구한다.

 

하나의 섬의 식량합계를 구하면 식량을 넣고, 0으로 초기화해준다.

 

 

재귀 함수이다.

 

탈출조건은 세가지다. 

1. 바다를 만났을때  'X'

2. 경계선을 넘엇을때,

3. 이미 방문했을때

 

이 3가지인 경우가 아니면, 방문체크를한뒤, 식량을 늘리면된다.

 

마무리 과정으로 아일랜드를 정렬하고 배열로 만들어준다.

 

섬이 없으면 -1을 반환하자.

문제풀이

import java.util.*;
class Solution {
    
List<Integer> island = new ArrayList<>();
int sum=0;
boolean[][] visited;
    public int[] solution(String[] maps) {
        int[] answer = {};
        
        visited= new boolean[maps.length][maps[0].length()];
        
        for(int i=0;i<maps.length;i++){
            String[] map = maps[i].split("");
            for(int j=0;j<map.length;j++){
                if(!visited[i][j]&&!map[j].equals("X")){
                    cal(i,j,maps);
                    island.add(sum);
                    sum=0;
                }else{
                    visited[i][j]=true;
                }
            }
        }
        
        if(island.size()==0){
            return new int[]{-1};
        }
        
        Collections.sort(island);
        
        answer=island.stream().mapToInt(i->i).toArray();
        
        return answer;
    }
    
    public void cal(int i , int j , String[] maps){
        
        if(maps[i].charAt(j)=='X'){
            return;
        }
        
        visited[i][j]=true;
        sum+=maps[i].charAt(j)-'0';
        
        if(i!=maps.length-1&&!visited[i+1][j]) cal(i+1,j,maps);
        if(i!=0&&!visited[i-1][j]) cal(i-1,j,maps);
        if(j!=maps[0].length()-1&&!visited[i][j+1]) cal(i,j+1,maps);
        if(j!=0&&!visited[i][j-1])cal(i,j-1,maps);
        
    }
}