[프로그래머스] 무인도여행 자바 풀이

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

프로그래머스

 

 

문제 풀이

어떤 독창적 풀이.. 그런 건 없습니다. 

그저 DFS로 풀었습니다.

dfs 기본 코드인데 유튜브에서 설명을 참고해서 풀었습니다.

https://www.youtube.com/watch?v=yQ7o1Y7X_Rg 

 

 

import java.util.*;

class Solution {
    static boolean[][] visited;
    int survive = 0;
    static int[][] d = {{-1,0},{1,0},{0,-1},{0,1}}; // 방향 
    public int[] solution(String[] maps) {
        List<Integer> answer = new ArrayList<>();
        visited = new boolean[maps.length][maps[0].length()];
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                if (maps[i].charAt(j) != 'X' && !visited[i][j]) {
                    bfs(i, j, maps);
                    answer.add(survive);
                }
            }
        }
        if (answer.size() == 0) return new int[] {-1};
        Collections.sort(answer);
        return answer.stream().mapToInt(i->i).toArray();
    }
    public int bfs(int startX, int startY, String[] maps) {
        Queue<int[]> queue = new LinkedList<>();
        survive = 0;
        visited[startX][startY] = true;
        queue.add(new int[]{startX, startY});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            survive += Integer.parseInt(maps[cur[0]].charAt(cur[1])+"");
            for (int i = 0; i < 4; i++) {
                int x = cur[0] + d[i][0], y = cur[1] + d[i][1];
                if (x < 0 || x > visited.length-1 || y < 0 || y > visited[0].length-1) continue;
                if (visited[x][y]) continue;
                if (maps[x].charAt(y) == 'X') continue;
                visited[x][y] = true;
                queue.add(new int[]{x,y});
            }
        }
        return survive;
    }
}

효율성은 그럭저럭입니다.

안녕히계세요뿅