[프로그래머스] LEVEL2 무인도 여행 JAVA

무인도 여행

문제링크

풀이

dfs
1. maps의 방문여부(isVisited), map의 크기 정보를 담은 N,M 정보, dx, dy(이동 방향 정보)를 초기화한다.
2. 이중 for문을 통해 위에서부터 오른쪽으로 한칸씩 이동하며 방문하지 않은 섬을 찾는다.
(maps[i].charAt(j) != 'X' && !isVisited[i][j])
3. 방문했다는 표시를 해준다. 또한 couter로 해당 섬의 며칠동안 머물 수 있는지에 대한 정보를 저장한다.

• dfs로 현재 위치, maps정보, 몇번째 섬인지(cntSeom)를 parameter로 넘긴다.

4. dfs 내부에서는 4방향으로 움직인다.

• testX, testY에 다음 이동 위치를 저장한다.
• 만약 다음 이동 위치가 maps 범위 안이고, 아직 방문하지 않은 섬이라면,
  해당 섬을 방문 표시하고, counter에 해당섬에 머물수 있는 날짜를 더한다.
  그리고 다음 dfs에 현재위치(testX, testY) 및 maps, cntSeom 정보를 넘긴다.

5. dfs를 반복한다.
6. 이중 for문을 통해 모든 섬을 방문한 후에는 counter를 통해 섬의 개수 및 각 섬에 최대로 머물수 있는 기간에 대한 정보가 담겨 있다.

• 만약 counter가 비어있다면 방문할 수 있는 섬이 아무것도 없다는 뜻이므로, 초기에 answer를 {-1}로 초기화 한후, return 한다.
• 만약 counter가 비어있지 않다면 방문 할 수 있는 섬이 있다드 뜻이므로, counter.values()를 list화 한 후 오름차순 정렬한다. answer array를 counter.values() (섬의 개수) 만큼의 크기로 초기화 한후, 순서대로 값을 저장하여 return 한다.

코드

GitHub 풀이

import java.util.*;

class Solution {
    public int N, M;
    public boolean [][] isVisited;
    public Map<Integer, Integer> counter;
    
    // 상, 우, 하, 좌
    public int[] dx = {-1, 0, 1, 0};
    public int[] dy = {0, 1, 0, -1};
    public int[] solution(String[] maps) {
        int[] answer = { -1 };
        
        N = maps.length;
        M = maps[0].length();
        isVisited = new boolean[N][M];
        counter = new HashMap<>();
        
        int cntSeom = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (maps[i].charAt(j) != 'X' && !isVisited[i][j]) {
                    isVisited[i][j] = true;
                    counter.put(cntSeom, maps[i].charAt(j) - '0');
                    dfs(i, j, maps, cntSeom++);
                }
            }
        }
        
        
        List<Integer> list = new ArrayList<>(counter.values());
        Collections.sort(list);
        
        if (!counter.isEmpty()) {
            answer = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                answer[i] = list.get(i);
            }
        }

        
        return answer;
    }
    
    public void dfs(int x, int y, String[] maps, int cntSeom) {
        
        for (int d = 0; d < 4; d++) {
            int testX = x + dx[d];
            int testY = y + dy[d];
            if (!(0 <= testX && testX < N && 0 <= testY && testY < M)) continue;
            if (maps[testX].charAt(testY) != 'X' && !isVisited[testX][testY]) {
                isVisited[testX][testY] = true;
                counter.put(cntSeom, counter.get(cntSeom) + maps[testX].charAt(testY) - '0');
                dfs(testX, testY, maps, cntSeom);
            }
        }
        
    }   
}