[java] 프로그래머스스쿨 연습문제 Lv.2 DFS 문제 모음

1. 무인도 여행

코딩테스트 연습 - 무인도 여행 | 프로그래머스 스쿨 (programmers.co.kr)

풀이

1. 깊이 우선 탐색(DFS) 아이디어를 활용한다. 2. 전역변수로 배열 dx, 배열 dy, 2차원 배열 map, 2차원 배열 visited, 정수형 변수 row, col, cnt=0을 선언한다. 3. maps의 원소들을 한글자씩 정수로 바꿔 map에 복사한다. 3-1. 만약 X라면 -1을 저장한다. 4. answer을 리스트로 선언한다. 5. dfs라는 함수를 생성한다. 5-1. 현재 위치에서 이동할 수 있는 인접한 위치로 이동해가며 cnt에 값을 더한다. 5-2. 이동할 수 있는 곳이 더이상 없다면 cnt를 반환한다. 6. 반복문을 통해 map[행][열]의 값이 -1이 아니고 방문한 적이 없다면 dfs(행, 열)를 asnwer에 저장한다. 6-1. 저장 후 cnt=0으로 초기화

회고

- dfs를 자바로 구현한건 처음이었지만,, 무난하게 했다! - 제발~~~~~~ 2차원 리스트 배열에서 범위좀 헷갈리지 말자!!!

코드 (접은 글)

import java.util.*;

class Solution {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] visited = new boolean[101][101];
    static int[][] map = new int[101][101];
    static int row, col;
    static int cnt = 0;

    public int dfs(int x, int y) {
        visited[x][y] = true;
        cnt += map[x][y];

        for (int i = 0; i < 4; i++) {
            if (x + dx[i] < 0 || x + dx[i] >= row || y + dy[i] < 0 || y + dy[i] >= col)
                continue;
            if (map[x + dx[i]][y + dy[i]] >= 0 && visited[x + dx[i]][y + dy[i]] == false)
                dfs(x + dx[i], y + dy[i]);
        }
        return cnt;
    }

    public int[] solution(String[] maps) {
        ArrayList<Integer> answer = new ArrayList<>();
        row = maps.length;
        col = maps[0].length();

        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length(); j++) {
                if (maps[i].substring(j, j + 1).equals("X"))
                    map[i][j] = -1;
                else
                    map[i][j] = Integer.parseInt(maps[i].substring(j, j + 1));
            }
        }


        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] > 0 && visited[i][j] == false) {
                    answer.add(dfs(i, j));
                    cnt = 0;
                }
            }
        }
        if (answer.size() < 1) {
            answer.add(-1);
            return answer.stream().mapToInt(i -> i).toArray();
        }
        Collections.sort(answer);
        return answer.stream().mapToInt(i -> i).toArray();
    }

}