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

문제

무인도 여행

📌 아이디어

X가 아닌 자연수만을 탐색하는 것이 문제의 핵심입니다. 탐색의 출발점과 도착점이 명확하기 때문에 전형적인 그래프 탐색 문제입니다.

저는 BFS 알고리즘을 활용해 문제를 해결했습니다. 먼저 입력 데이터가 2차원 배열이 아니기 때문에 1차원을 2차원으로 변환해주는 과정을 진행했습니다.

변환 과정

arr = new char[maps.length][maps[0].length()];

for (int i = 0; i<maps.length; i++) {
    for (int j = 0; j<maps[i].length(); j++) {
        arr[i][j] = maps[i].charAt(j);
    }
}

변환 후에는 큐를 활용한 BFS 알고리즘을 작성했습니다. 상하좌우로 이동할 수 있도록 하였고, 아래와 같은 조건을 추가하여 만족하는 경우에만 큐에 추가하여 탐색을 진행했습니다.

1. 이동 한 위치가 그래프를 벗어나지 않은 경우
2. 이동 한 위치를 방문한 적이 없는 경우
3. 이동 한 위치가 X 가 아닌 경우

📌 코드

import java.util.*;

class Solution {
    
    char[][] arr;
    boolean[][] visited;
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    static PriorityQueue<Integer> result = new PriorityQueue<>();
    
    class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public void bfs(int ci, int cj) {
        Queue<Node> que = new LinkedList<Node>();
        que.add(new Node(ci, cj));
        visited[ci][cj] = true;
        
        int sum = Character.getNumericValue(arr[ci][cj]);
        
        while (!que.isEmpty()) {
            Node node = que.poll();
            
            for (int i = 0; i<4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                if (nx >= 0 && nx < arr.length && ny >= 0 && ny < arr[0].length) {
                    if (arr[nx][ny] != 'X' && visited[nx][ny] == false) {
                        visited[nx][ny] = true;
                        que.add(new Node(nx, ny));
                        sum += Character.getNumericValue(arr[nx][ny]);
                    }
                }
            }
            
        }
        result.add(sum);
    }
    
    public int[] solution(String[] maps) {
        int[] answer = {};
        arr = new char[maps.length][maps[0].length()];
        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++) {
                arr[i][j] = maps[i].charAt(j);
            }
        }
        
        for (int i = 0; i<arr.length; i++) {
            for (int j = 0; j<arr[0].length; j++) {
                if (arr[i][j] != 'X' && visited[i][j] == false) {
                    bfs(i, j);
                }
            }
        }
        
        if (result.isEmpty()) {
            result.add(-1);
        }
        answer = new int[result.size()];
        for (int i = 0; i<answer.length; i++) {
            answer[i] = result.poll();
        }
        return answer;
    }
}

✏️ TIP

1 . 큐에는 두 개의 좌표가 필요하기 때문에 새로운 Node 클래스를 작성해 탐색을 진행했습니다.

class Node {
    int x;
    int y;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

que.add(new Node(nx, ny));
Node node = que.poll();

2. 그래프의 요소는 char 타입이므로 int로 변환하는 과정을 진행했습니다. 변환하는 방법은 크게 2가지가 있습니다.

int num = c - '0'; // char 정수 - 48 = 실제 정수
Character.getNumericValue(c)

3. 처음에는 List를 활용해 값을 추가하여 정렬 후 정답을 반환했지만, PriorityQueue를 활용해 더욱 간편하게 문제를 해결했습니다.

PriorityQueue<Integer> pq1 = new PriorityQueue<>();
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());

pq.size();
pq.add(tmp);
pq.poll();

피드백 및 개선점은 댓글을 통해 알려주세요😊