[프로그래머스] 무인도 여행 / 자바(Java)

문제

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

프로그래머스

 

---

해설

상하좌우로 연결된 같을 모두 더하고 떨어져있는 요소들을 오름차순으로 정렬하면되는 간단한 4방탐색와 완전탐색을 섞은 문제입니다.

3가지 코드들을 이용해 문제를 해결할 수 있습니다.

1. 입력을 다루기 쉽게 2차원 배열로 생성(map)
2. 4방탐색을 시작할 위치를 반복을 통해 선정
3. 4방탐색과 BFS
4. 리스트를 배열로 변환, 정렬

 

1번. 입력을 다루기 쉽게 2차원 배열로 생성

문제에서 주어진 maps 배열을 String 배열이기에 원하는 위치의 값을 조회, 수정하는데 charAt등 추가적인 함수가 필요합니다. 따라서 쉽게 사용 가능하도록 int형 2차원배열로 가공해 줍니다. 이때 'X'는 maps에는 1~9의 숫자만 들어간다는 조건에 따라 구별하기 쉽도록 0을 대신 넣어줍니다. 이때 특정 위치가 이전에 방문했는가 여부를 파악하기 위해 boolean형 2차원배열을 같이 만들어 줍니다.

        int[][] map = new int[maps.length][maps[0].length()];
        boolean[][] checker = new boolean[maps.length][maps[0].length()];
        
        for(int i=0;i<maps.length;i++){
            for(int j=0;j<maps[0].length();j++){
                char cur = maps[i].charAt(j);
                if(cur=='X'){
                    map[i][j] = 0;
                }else{
                    map[i][j] = cur-48;
                }
            }
        }

 

2번. 4방탐색을 시작할 위치를 반복을 통해 선정

중첩 for문을 사용해 2차원 배열을 하나씩 훑을 수 있도록 지정합니다. 가로, 세로 위치가 햇깔릴 수 있어 r, c를 인덱스로 정합니다. 각 섬별로 연산을 해줘야 하기 때문에 해당 위치가 X가 아닌가 와 이미 방문한 적 있는가, 2가지로 조건을 두어 탐색을 시작하여 최소한의 연산만 실행하도록 합니다.

        for(int r=0;r<map.length;r++){
            for(int c=0;c<map[0].length;c++){
                if(map[r][c]==0 || checker[r][c]) continue;
                answerList.add(fourWaySeek(r,c,map,checker));
                
            }
        }

 

3번. 4방탐색과 BFS

특정 지점에서 연결된 모든 칸을 찾기위해 완전탐색과 2차원 배열상에서 해내기 위해 4방탐색을 사용합니다.

특정 지점과 붙어있는 4방향의 블럭이 유효한가 판별하고, 유효할 경우 큐에 넣어 반복가능하도록 합니다. 유효여부를 판별하기 위해 특점 지점 근처의 블럭이 범위를 벗어나지 않는가, 해당 위치가 X가 아닌가, 이미 방문한 적이 있는가, 3가지 조건을 보고 판단해 줍니다. 특정 지점을 꺼낼 때 해당 위치의 숫자를 더해주어 각 섬별 총합을 구하도록하고 리스트에 추가해주도록 합니다.

public int[] dr = {1,0,-1,0};
public int[] dc = {0,1,0,-1}; 

public int fourWaySeek(int r, int c, int[][] map, boolean checker[][]){
        int sum=0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {r,c});
                
        while(!q.isEmpty()){
            int[] cur = q.poll();
            sum+=map[cur[0]][cur[1]];
            checker[cur[0]][cur[1]] = true;
            for(int k=0;k<4;k++){
                int newr = cur[0]+dr[k];
                int newc = cur[1]+dc[k];
                if(newr>=0 && newc >=0 &&
                   newr < map.length && newc < map[0].length &&
                   !checker[newr][newc] && map[newr][newc]!=0){
                    checker[newr][newc] =true;
                    q.add(new int[] {newr,newc});
                }
            }
        }
        return sum;      
    }

 

4번. 리스트를 배열로 변환, 정렬

얻은 섬별 총합 리스트를 출력에 맞기 배열로 변환하고 정렬해줍니다.

        answer = answerList.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(answer);
        return answer.length > 0 ? answer : new int[] {-1};

 

---

코드

import java.util.*;
class Solution {
    
    public int[] dr = {1,0,-1,0};
    public int[] dc = {0,1,0,-1};  
    
    public int[] solution(String[] maps) {
        int[] answer = {};
        List<Integer> answerList = new ArrayList<>();
        int[][] map = new int[maps.length][maps[0].length()];
        boolean[][] checker = new boolean[maps.length][maps[0].length()];
        
        for(int i=0;i<maps.length;i++){
            for(int j=0;j<maps[0].length();j++){
                char cur = maps[i].charAt(j);
                if(cur=='X'){
                    map[i][j] = 0;
                }else{
                    map[i][j] = cur-48;
                }
            }
        }
        
        for(int r=0;r<map.length;r++){
            for(int c=0;c<map[0].length;c++){
                if(map[r][c]==0 || checker[r][c]) continue;
                answerList.add(fourWaySeek(r,c,map,checker));
                
            }
        }
        answer = answerList.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(answer);
        return answer.length > 0 ? answer : new int[] {-1};
    }
    
    public int fourWaySeek(int r, int c, int[][] map, boolean checker[][]){
        int sum=0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {r,c});
                
        while(!q.isEmpty()){
            int[] cur = q.poll();
            sum+=map[cur[0]][cur[1]];
            checker[cur[0]][cur[1]] = true;
            for(int k=0;k<4;k++){
                int newr = cur[0]+dr[k];
                int newc = cur[1]+dc[k];
                if(newr>=0 && newc >=0 &&
                   newr < map.length && newc < map[0].length &&
                   !checker[newr][newc] && map[newr][newc]!=0){
                    checker[newr][newc] =true;
                    q.add(new int[] {newr,newc});
                }
            }
        }
        return sum;      
    }
}