[Java] 프로그래머스 : DFS

다음은 알고리즘 DFS(Depth First Search)에 대한 예시입니다.

프로그래머스에서 코딩테스트를 하며 알고리즘에 대한 부분이 부족하다는 것을 깨달았습니다. 이는 알고리즘에 대한 저의 첫걸음입니다.

import java.util.*;

class Solution {
    public int[] solution(String[] maps) {
        int rows = maps.length;
        int cols = maps[0].length();
        int[][] grid = new int[rows][cols];
        boolean[][] visited = new boolean[rows][cols];
        List<Integer> result = new ArrayList<>();

        // 숫자형 배열로 변환
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
            	grid[i][j] = Character.isDigit(maps[i].charAt(j)) ? Character.getNumericValue(maps[i].charAt(j)) : 0;
            }
        }

        // DFS 실행
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] > 0 && !visited[i][j]){
                    int sum = dfs(grid, visited, i, j);
                    result.add(sum);
                }
            }
        }

        Collections.sort(result);
        if(result.size() == 0) result.add(-1);
        int[] answer = result.stream().mapToInt(Integer::intValue).toArray();
        return answer;
    }

    // DFS 메소드
    public int dfs(int[][] grid, boolean[][] visited, int row, int col){
        int rows = grid.length;
        int cols = grid[0].length;
        int[] dr = {-1,1,0,0};
        int[] dc = {0,0,-1,1};
        int sum= grid[row][col];
        visited[row][col] = true;

        for (int d = 0; d < 4; d++) {
            int nr = row + dr[d];
            int nc = col + dc[d];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] > 0 && !visited[nr][nc]) {
            	sum += dfs(grid, visited, nr, nc);
            }
        }

        return sum;
    }
}

 

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