무인도 여행 (DFS)

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

프로그래머스

 

문제 풀이

• 가로의 최대 길이 100, 세로의 최대 길이 100 -> N^2의 시행 횟수가 10000이므로 O(N^2) 알고리즘까지 사용 가능
• 2차원 배열에 대한 탐색이며, 되돌아오지 않음 -> DFS

문제가 요구 알고리즘이 쉽기도 했고, 이제 DFS나 백트래킹을 요구하는 문제는 바로 풀이법이 보이는 것 같다.

힌트 없이 시간 내에 풀었다.

 

 

작성한 코드 (정답)

import java.util.*;

class Solution {
       public int[] solution(String[] maps) {

        List<Integer> answer = new ArrayList<>();

        int xSize = maps.length;
        int ySize = maps[0].split("").length;

        String[][] mapsArray = new String[xSize][ySize];

        for (int i = 0; i < xSize; i++) {
            String[] temp = maps[i].split("");

            for (int j = 0; j < ySize; j++) {
                mapsArray[i][j] = temp[j];
            }
        }

        boolean[][] visited = new boolean[xSize][ySize];

        for (int i = 0; i < xSize; i++) {
            for (int j = 0; j < ySize; j++) {

                if (visited[i][j] || mapsArray[i][j].equals("X")) continue;

                // 전역변수 만들기 싫어서 배열로 구현
                int[] result = {0};

                dfs(mapsArray, i, j, visited, xSize, ySize, result);

                answer.add(result[0]);
            }
        }
           
        if (answer.isEmpty()) answer.add(-1);


        Collections.sort(answer);

        return answer.stream().mapToInt(i -> i).toArray();
    }

    public void dfs(String[][] mapsArray, int x, int y, boolean[][] visited, int xSize, int ySize, int[] result) {

        result[0] += Integer.parseInt(mapsArray[x][y]);
        visited[x][y] = true;

        // 상
        if (y-1 >= 0 && !visited[x][y-1] && !mapsArray[x][y-1].equals("X")) {
            dfs(mapsArray, x, y-1, visited, xSize, ySize,result);
        }

        // 하
        if (y+1 < ySize && !visited[x][y+1] && !mapsArray[x][y+1].equals("X")) {
            dfs(mapsArray, x, y+1, visited, xSize, ySize,result);
        }

        // 좌
        if (x-1 >= 0 && !visited[x-1][y] && !mapsArray[x-1][y].equals("X")) {
            dfs(mapsArray, x-1, y, visited, xSize, ySize,result);
        }

        // 우
        if (x+1 < xSize && !visited[x+1][y] && !mapsArray[x+1][y].equals("X")) {
            dfs(mapsArray, x+1, y, visited, xSize, ySize,result);
        }

    }
}

 

 

더 좋은 방법

델타 배열을 적용해서 코드 중복을 줄이며 코딩 할 수 있다.

    public void dfs(String[][] mapsArray, int x, int y, boolean[][] visited, int xSize, int ySize, int[] result) {

        result[0] += Integer.parseInt(mapsArray[x][y]);
        visited[x][y] = true;

        int[] dx = {-1,1,0,0};
        int[] dy = {0,0,-1,1};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (ny >= 0 && ny < ySize && !visited[nx][ny] && !mapsArray[nx][ny].equals("X")) {
                dfs(mapsArray, nx, ny, visited, xSize, ySize,result);
            }
        }
    }