[프로그래머스] Lv.2 무인도 여행JAVA 풀이

 

문제 Lv.2 무인도 여행

: 지도 = 1 x 1 크기의 사각형으로 이루어진 직사각형 격자 형태

  격자  구성 = X, 숫자 (1 ~ 9)

     - X = 바다

     - 숫자 = 무인도 (상, 하, 좌, 우 붙어있는 애들은 하나의 무인도, 대각선은 다른땅) 

: 하나의 무인도 숫자 합 = 해당 무인도에서 최대로 머무를 수 있는 기한 (오름차순으로 출력)

  무인도가 없는 경우 = -1 출력 

 

:  maps = 지도 (문자열 배열)

 

 

[지도 배열 예시]

 

 

 [알고 가기]

 < DFS >

 

-  깊이 우선 탐색

-  그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

-  스택 or 재귀함수 이용

 

-  제일 깊게 내려간 뒤 더이상 갈 수 없을 때 옆으로

   이동해서 다시 깊게 내려가기를 반복

-  구현 : DFS (간단) > BFS

 

-  검색 속도 : BFS  > DFS (느림)

 

 

출처 https://developer-mac.tistory.com/64

 

 [코드]

import java.util.*;

class Solution {
    static int X = 0;
    static int Y = 0;
    static int day = 0;

    public int[] solution(String[] maps) {
        X = maps.length;
        Y = maps[0].length();
        int[][] map = new int[X][Y];
        for(int i = 0; i < X; i++) {
            char[] c = maps[i].toCharArray();
            for(int j = 0; j < c.length; j++) {
                if(c[j] == 'X') {
                    map[i][j] = 0;
                } else {
                    map[i][j] = c[j] - '0';
                }
            }
        }

        List<Integer> days = new ArrayList<>();
        boolean[][] visited = new boolean[X][Y];
        for(int i = 0; i < X; i++) {
            for(int j = 0; j < Y; j++) {
                if(!visited[i][j] && map[i][j] > 0) {
                    dfs(map, visited, i, j);
                    days.add(day);
                    day = 0; 
                }
            }
        }
        if(days.isEmpty()) {
             return new int[]{-1};
        }
        Collections.sort(days);
        int[] answer = new int[days.size()];
        for(int i = 0; i < answer.length; i++) {
            answer[i] = days.get(i);
        }

        return answer;
    }

    private void dfs(int[][] map, boolean[][] visited, int x, int y) {
        day += map[x][y];
        visited[x][y] = true;
        int[] upAndDown = {1, -1, 0, 0};
        int[] leftAndRight = {0, 0, 1, -1};

        for(int i = 0; i < 4; i++) {
            int newX = x + upAndDown[i];
            int newY = y + leftAndRight[i];

            if(newX < 0 || newY < 0 || newX >= X || newY >= Y) {
                continue;
            }

            if(!visited[newX][newY] && map[newX][newY] > 0) {
                dfs(map, visited, newX, newY);
            }
        }
    }
}

       

:   static int X = 0; 
    static int Y = 0;
    static int day = 0;

:   public int[] solution(String[] maps) {  2차원 배열 만들기
          X = maps.length;
          Y = maps[0].length();
          int[][] map = new int[X][Y];
       

:   for(int i = 0; i < X; i++) {  X부터 시작
          char[] c = maps[i].toCharArray();  문자 하나씩 뜯어보기
          for(int j = 0; j < c.length; j++) {  
                if(c[j] == 'X') {  문자가 X와 같다면
                    map[i][j] = 0;  2차원 배열에 0으로 등록
                } else {  아닐 경우
                    map[i][j] = c[j] - '0';  문자에서 - 0
                }
          }
    }

:   List<Integer> days = new ArrayList<>();  List 사용
    boolean[][] visited = new boolean[X][Y];  boolean[][] visited 
    for(int i = 0; i < X; i++) {  X부터 시작
            for(int j = 0; j < Y; j++) {  Y도 시작
                if(!visited[i][j] && map[i][j] > 0) {  방문한 적이 없고, 무인도일 경우
                    dfs(map, visited, i, j);  dfs 설정
                    days.add(day);  day 추가
                    day = 0;  day 0으로 초기설정
                }
            }
    }

:   if(days.isEmpty()) {  무인도 없는 경우는 -1 출력
             return new int[]{-1};
     }

 

:   Collections.sort(days);  오름차순 정렬
    int[] answer = new int[days.size()];
    for(int i = 0; i < answer.length; i++) {
           answer[i] = days.get(i);
     }
     return answer;
     }

:   private void dfs(int[][] map, boolean[][] visited, int x, int y) {  머무를 수 있는 날짜 계산
        day += map[x][y];  해당 위치에서의 값으로 day 갱신 
        visited[x][y] = true;
        int[] upAndDown = {1, -1, 0, 0};  상, 하
        int[] leftAndRight = {0, 0, 1, -1};  좌, 우

:   for(int i = 0; i < 4; i++) {
            int newX = x + upAndDown[i];
            int newY = y + leftAndRight[i];

            if(newX < 0 || newY < 0 || newX >= X || newY >= Y) { 범위 확인
                continue;
            }

            if(!visited[newX][newY] && map[newX][newY] > 0) { 방문한 적이 없고 무인도일 경우
                dfs(map, visited, newX, newY); dfs
            }
    }

 

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

 

프로그래머스

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *