[LeetCode- Part. 1] 7. 금광 찾기 #

 

https://leetcode.com/problems/path-with-maximum-gold/submissions/

Path with Maximum Gold - LeetCode

 

 

최대 금 찾기

1. 위치한 셀에서 모든 금을 가질 수 있다

2. 자신의 위치에서 왼쪽, 오른쪽, 위, 아래로 한칸 이동 가능.

3. 같은 셀을 두 번 이상 방문 할 수 없다

4. 0이 있는 셀은 방문할 수 없다

5. 모든 위치에서 금 수집을 시작하고 중지 할 수 있다

 

 

(1) DFS- 클래스 작성

class Point{
    public int x, y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
    
}
class Solution {
    int answer=0;
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    boolean[][] visited;
    int n,m;
    public int getMaximumGold(int[][] grid) {
        //boolean배열을 true로 모두 바꾼 후, 돌아오면서 false로 다시 바꾼다.
        n=grid.length;
        m=grid[0].length;
        visited=new boolean[n][m];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]!=0){
                    DFS(grid, new Point(i,j), 0);
                }
            }
        }
        return answer;
    }
    public void DFS(int[][] grid, Point point, int val){
        if(!isValid(grid, point)) return;
        
        visited[point.x][point.y]=true;
        
        val=val+grid[point.x][point.y];
        answer=Math.max(answer,val);
        
        for(int[] dir:dirs) {
            Point np=new Point(point.x+dir[0], point.y+dir[1]);
            DFS(grid, np,val);
        }
        
        //true로 바꾼 배열을 다시 false로
        visited[point.x][point.y]=false;
        
    }
    public boolean isValid(int[][] grid,Point point){
        if(point.x<0 || point.y<0||point.x>=n|| point.y>=m|| grid[point.x][point.y]==0||visited[point.x][point.y]) return false;
        return true;
    }
}

 

(2) DFS - 배열

class Solution {
    boolean[][] visited;
    int n,m;
    int answer=0;
    int[][]dirs={{0,1},{1,0},{-1,0},{0,-1}};
    public int getMaximumGold(int[][] grid) {
        n=grid.length;
        m=grid[0].length;
        
        visited=new boolean[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                DFS(grid,i,j,0);
            }
        }
        return answer;
    }
    public void DFS(int[][] grid, int x, int y, int val){
        if(!isValid(grid, x,y)) return;
        
        val+=grid[x][y];
        visited[x][y]=true;
        answer=Math.max(val,answer);
        
        for(int[]dir:dirs){
            int nx=x+dir[0];
            int ny=y+dir[1];
            
            DFS(grid, nx, ny,val);
        }
        visited[x][y]=false;
        
    }
    public boolean isValid(int[][] grid, int x, int y){
        if(x<0||y<0||x>=n||y>=m||grid[x][y]==0||visited[x][y]) return false;
        return true;
    }
}