문제

https://school.programmers.co.kr/learn/courses/30/lessons/154540

---

입력

String배열형태로 구성된 map

["X591X","X1X5X","X231X", "1XXX1"]

---

출력

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return.
만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return

---

풀이

제한조건

• 3 ≤ maps의 길이 ≤ 100
• 3 ≤ maps[i]의 길이 ≤ 100
• maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
• 지도는 직사각형 형태입니다.

접근방법

단순 탐색문제이다.

BFS 또는 DFS를 활용하여 풀 수 있다.
너비 우선 탐색(BFS) 또는 깊이 우선 탐색(DFS)에 대한 개념이 없다면 먼저 공부하고 오자.

- DFS 주의 -
무인도의 전체가 음식으로 구성된 경우 100x100의 사이즈 이므로 함수 스택을 이용한 DFS는 불가능 할 수 있다. 스택을 활용하자.

해당 풀이에서는 BFS를 활용한다.
순서는 다음과 같다.

1. maps를 순회하며 식량이 있는곳을 찾는다.
2. 식량이 있고 해당 지점에서 탐색한적이 없다면 탐색을 시작한다.
	a. 탐색 과정에서 발견하는 모든 식량을 더해서 반환한다.
3. 탐색이 완료되었다면, 오름차순으로 정렬해서 반환한다.
	a. 만약 탐색가능한것이 없었다면, -1을 반환한다.

위의 로직만 잘 수행한다면, 해당 문제에서 주의할만한 부분은 없다.

---

코드

import java.util.*;

class Point{
    int x;
    int y;
    Point(int a, int b){
        x = a;
        y = b;
    }
}

class Solution {
    int N, M;
    boolean[][] visit;
    List<Integer> list;
    public int[] solution(String[] maps) {
        N = maps.length;
        M = maps[0].length();
        visit = new boolean[N][M];
        list = new ArrayList();
        
        for(int i = 0 ; i < N; ++i){
            for(int j = 0 ; j < M; ++j){
                // 해당 지점에 음식이 있고, 방문한적이 없다면 탐색을 시작한다.
                if(hasFood(maps[i].charAt(j)) && !visit[i][j]){
                    list.add(search(maps, i, j));
                }
            }
        }
        
        // 조건에 따라, 무인도가 없는 경우 -1
        if(list.isEmpty())
            list.add(-1);
        
        // 오름차순으로 정렬
        return list.stream()
                .sorted()
                .mapToInt(i->i)
                .toArray();
    }
    
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    
    // 해당 지점에서 탐색하여 머물 수 있는 최대 일 수를 반환.
    public int search(String[] maps, int startX, int startY){
        int result = 0;
        result += maps[startX].charAt(startY)-'0';
        visit[startX][startY] = true;
        Queue<Point> q = new ArrayDeque();
        q.add(new Point(startX, startY));
        
        while(!q.isEmpty()){
            Point cur = q.poll();
            // 인접 지역으로 탐색
            for(int d = 0 ; d < 4; ++d){
                int nextX = cur.x + dx[d];
                int nextY = cur.y + dy[d];
                // 범위 내부면서, 음식이 있고, 방문한적이 없다면 해당 지점에서 탐색
                if(isInRange(nextX, nextY) && hasFood(maps[nextX].charAt(nextY)) && !visit[nextX][nextY]){
                    visit[nextX][nextY] = true;
                    result += maps[nextX].charAt(nextY)-'0';
                    q.add(new Point(nextX, nextY));
                }
            }
        }
        return result;
    }
    
    public boolean hasFood(char c){
        if('0'<= c  && c <='9')
            return true;
        return false;
    }
    
    public boolean isInRange(int x, int y){
        if(0 <= x && x < N && 0 <= y && y <M)
            return true;
        return false;
    }
}