[Lv.2] 무인도 여행 : Java

 

프로그래머스

 

 

 

이해하기

방금 막 비슷한 문제를 풀었으니 이 문제는 혼자서 풀 수 있겠지! 하고 덤벼들었다가... 🥹

이것도 아이디어는 비슷했다. BFS 사용과 사방탐색!

 

1. X면 바다니까 탐색 X
2. X가 아니면 BFS
3. BFS 끝나면 list에 result 담기

로 정리해보았는데 이 또한 구현에 실패했다

 

 

문제풀이

[Programmers] 무인도 여행(Lv.2) - Java

이번에 참고한 건 이 블로그!

 

처음 스스로 시도했을 때는 char[][] 배열로 문자열을 정리하지 않고, maps 문자열 그대로 charAt을 사용했었는데, 이 분은 이차원 배열로 다시 정리하셨다. charAt보다 훨씬 편한듯...

 

이 분의 아이디어는 다음과 같았다.

설명만 보면 너무 쉬운데... ㅜㅅㅜ

 

import java.util.*;

class Solution {
    int[] dX = {1, -1, 0, 0};
    int[] dY = {0, 0, 1, -1};

    char[][] mapToChar;
    boolean[][] visited;


    public int[] solution(String[] maps) {
        List<Integer> list = new ArrayList<>();
        mapToChar = new char[maps.length][maps[0].length()];
        visited = new boolean[maps.length][maps[0].length()];

        for (int i = 0; i < maps.length; i++) {
            mapToChar[i] = maps[i].toCharArray();
        }

        for (int i = 0; i < mapToChar.length; i++) {
            for (int j = 0; j < mapToChar[i].length; j++) {
                if (!visited[i][j] && mapToChar[i][j] != 'X') {
                    list.add(bfs(i, j));
                }
            }
        }

        if (list.size() == 0) {
            list.add(-1);
        }

        Collections.sort(list);
        return list.stream().mapToInt(i -> i).toArray();
    }

    public int bfs(int x, int y) {
        int sum = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cX = current[0];
            int cY = current[1];
            sum += mapToChar[cX][cY] - '0';

            for (int i = 0; i < 4; i++) {
                int nX = cX + dX[i];
                int nY = cY + dY[i];

                if (nX < 0 || nX > mapToChar.length - 1 || nY < 0 || nY > mapToChar[0].length - 1) {
                    continue;
                }

                if (!visited[nX][nY] && mapToChar[nX][nY] != 'X') {
                    visited[nX][nY] = true;
                    queue.offer(new int[]{nX, nY});
                }
            }
        }
        return sum;
    }
}

 

이 코드도 하나하나 생각해보자.

 

    int[] dX = {1, -1, 0, 0};
    int[] dY = {0, 0, 1, -1};

 

일단 똑같이 사방탐색 좌표.

 

    char[][] mapToChar;
    boolean[][] visited;

 

처음엔 이 부분을 solution 함수 안에 적어야하지 않나? 했지만, 그렇게 되면 매개변수로 또 넘겨줘야하고 복잡해지니 이렇게 밖에 선언하는게 더 편한 것 같다.

 

        List<Integer> list = new ArrayList<>();
        mapToChar = new char[maps.length][maps[0].length()];
        visited = new boolean[maps.length][maps[0].length()];

 

답을 담을 list 선언해주고, mapToChar과 visited를 초기화해준다.

 

        for (int i = 0; i < maps.length; i++) {
            mapToChar[i] = maps[i].toCharArray();
        }

 

for문을 돌며 mapToChar로 내용을 옮겨주는데, 나였다면 또 charAt을 사용했을 것 같다...

(아는 게 charAt밖에 없어서 흑흑) 이런 방법도 잘 알아둬야지.

 

        for (int i = 0; i < mapToChar.length; i++) {
            for (int j = 0; j < mapToChar[i].length; j++) {
                if (!visited[i][j] && mapToChar[i][j] != 'X') {
                    list.add(bfs(i, j));
                }
            }
        }

 

이 부분!! 나는 이 부분을 bfs 함수 안에서 가려내려고 고민했는데 이렇게 구현하는게 훨 편한 것 같다!

mapToChar을 돌며 방문한 적 없고 (and) 'X'가 아닌 곳은 bfs() 한 후 결과값을 list에 add한다.

 

이제 bfs 함수를 살펴보자.

 

        int sum = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

 

총합을 구해야하니 sum을 선언해주고 queue를 만들어준다.

여기서는 매개변수로 들어온 x, y (위에서 이야기한 방문한 적 없고 'X'가 아닌 곳의 좌표!)를 queue에 offer해주고 visited[x][y]를 true로 만들어준다.

 

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cX = current[0];
            int cY = current[1];
            sum += mapToChar[cX][cY] - '0';

 

이 부분은 전 문제인 게임 맵 최단거리와 비슷하지만 sum부분이 추가되었다.

char값이니 '0'을 빼준 int값을 더해준다.

 

            for (int i = 0; i < 4; i++) {
                int nX = cX + dX[i];
                int nY = cY + dY[i];

                if (nX < 0 || nX > mapToChar.length - 1 || nY < 0 || nY > mapToChar[0].length - 1) {
                    continue;
                }

 

이 부분도 전 문제와 비슷하니 넘어가겠다.

 

                if (!visited[nX][nY] && mapToChar[nX][nY] != 'X') {
                    visited[nX][nY] = true;
                    queue.offer(new int[]{nX, nY});
                }

 

사방탐색 후 값인 nX, nY 좌표를 방문한 적 없고 (and) 'X'가 아니라면 if문 내부를 실행한다.

방문여부를 true로 바꿔주고 queue에 해당 좌표를 offer해준다.

 

        return sum;

 

그렇게 while문이 끝나면 sum값을 리턴!

 

        if (list.size() == 0) {
            list.add(-1);
        }

 

다시 solution 함수로 올라가서 이 부분을 보면 list가 아예 비어있을 경우에는 -1을 add해서 [-1]과 같이 return 되게 한다.

 

        Collections.sort(list);
        return list.stream().mapToInt(i -> i).toArray();

 

Collection.sort로 오름차순 정렬해준 후 return해야 하는데, 여기서는 int[]를 return하도록 되어있으니 변환해주어야 한다.

이 부분은 따로 구글링해서 찾았는데, 이제껏 list를 하나하나 for문을 통해 배열로 바꿔주었던 것보다 훨씬 편하다.

단 한 번에 떠올리기가 조금 어렵다ㅠ

 

list.stream().mapToInt(i -> i).toArray()

알아두면 활용하기 좋을 것 같다.

 

 

앞의 문제랑 거~의 비슷하지만? 조금 달라졌다고 바로 못 푸는 ^^...

그래도 조금은 감이 잡히는 것 같다.