[99클럽 코테 스터디 32일차 TIL] 무인도 여행 - Java [자바][프로그래머스]

 

 

📜 문제 내용

 

🤔 과정

• 방문 배열과 DFS로 해결할 수 있었다. 
• String으로 계속 확인하는 과정 대신 'X'를 숫자 0으로 바꿔서 정수형 2차원 배열 map에 저장한다. 
• 방문 배열을 확인하면서 dfs 반복 

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

import java.util.*;

class Solution {
    public static int[] dr = {1,-1,0,0}; // 델타
    public static int[] dc = {0,0,1,-1};
    public static int[][] map; // 무인도 식량 지도
    public static boolean[][] visited; // 방문배열

    public int[] solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        
        map = new int[n][m];
        visited = new boolean[n][m];
        List<Integer> stay = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String tmp = maps[i];
            
            // X라면 0으로 저장하고 아니면 숫자 저장
            for (int j = 0; j < m; j++) {
                 map[i][j] = (tmp.charAt(j) == 'X') ? 0 : tmp.charAt(j) - '0';
            }
        }
        
        // 완전탐색 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && map[i][j] != 0) {
                   // 머무를 수 있는 일자 cnt 
                   int cnt = dfs(i, j); 
                   stay.add(cnt);
                }
            }
        }
        
        // stay가 비어있으면, 지낼 수 있는 무인도 X 
        if (stay.isEmpty()) {
            return new int[] {-1};
        }
        
        // 머물 수 있는 일자 저장 및 오름차순 정렬 
        int[] answer = new int[stay.size()];
        for (int i = 0; i < stay.size(); i++) {
            answer[i] = stay.get(i);
        }
        Arrays.sort(answer);
        
        return answer;
    }
	
    // dfs, r은 행, c는 열
    public int dfs(int r, int c) {
    	// 방문체크 
        visited[r][c] = true;
        int cnt = map[r][c];
        
        // 4방 탐색
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (boundaryCheck(nr,nc) && !visited[nr][nc] && map[nr][nc] != 0) {
                cnt += dfs(nr, nc);
            } 
        }
        
        return cnt;
    }
    
    // 무인도 경계 체크
    public boolean boundaryCheck(int r, int c) {
        return r >= 0 && c >= 0 && r < map.length && c < map[0].length;
    }
}

 

🔗 문제 링크

• 프로그래머스 - 무인도 여행 (링크) 

프로그래머스