[java, BFS] 프로그래머스 - 무인도 여행

📖 풀이한 문제

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

프로그래머스

 

---

💡 문제에서 사용된 알고리즘

• DFS

---

📜 코드

import java.util.*;
class Solution {
    static boolean [][] visited;
    static char [][] map;
    static int w, h;
    public int[] solution(String[] maps) {
        int[] answer = {-1};
        h = maps.length;
        w = maps[0].length();
        // 무인도 방문 체크하기 위하여
        visited = new boolean[h][w];
        // 정답 넣기
        ArrayList<Integer> list = new ArrayList<>();
        
        // maps를 char 이차원 배열로 바꾸기
        map = new char[h][w];
        for (int i = 0; i < h; i++) {
            map[i] = maps[i].toCharArray();
            
        }
        
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
               
                if (map[i][j] != 'X' && !visited[i][j]) {
                    list.add(findMax(i, j));
                }
            }
        }
        int size = list.size();
        if (list.get(0) != -1) {
            Collections.sort(list);
            answer = new int[size];
            for (int i = 0; i < size; i++) {
                answer[i] = list.get(i);
            }
        }
        
        System.out.println(list);
        
        return answer;
    }
    
    public int findMax(int x, int y) {
        
        int max = (map[x][y] - '0');
        // 상하좌우
        int [] dx = {-1, 1, 0, 0};
        int [] dy = {0, 0, -1, 1};
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x, y});
        visited[x][y] = true;
        while(!que.isEmpty()) {
            int[] now = que.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                if (nx >=0 && ny >= 0 && nx < h && ny < w && map[nx][ny] != 'X' && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    que.add(new int[]{nx, ny});
                    max += (map[nx][ny] - '0');   
                }
            } 
        }
        return max;
    }
}

---

📜 코드 설명

1. String [] maps → char [][] map의 형태로 바꿔줌
2. map을 돌며 X가 아니고 방문을 하지 않았을 때 무인도이므로 findMax 메서드를 사용하여 무인도의 최대 살 수 있는 날짜를 찾아준다. 그 값을 리스트에 넣어줬다.
3. findMax는 DFS를 사용하여 구해주었다.

• Queue를 사용하여 현재 큐에서 꺼낸 값의 상하좌우를 확인하여 배열 안에 있고 X가 아니고 방문을 하지 않았더라면
  • 다음 이동한 값의 인덱스를 방문확인해 준다
  • 큐에 다음 이동할 값의 인덱스를 넣어준다.
  • max(최대 살 수 있는 날짜)에 값을 더해준다.

1. answer의 초기값으로 {-1}으로 설정해 준다. → 무인도가 없을 때를 위하여

• list의 값이 있더라면 리스트를 오름차순 정렬해 주고 anwer에 값을 넣어주었다.