[소프티어] 함께하는 효도 자바 풀이 dfs 쉽게 설명 쉬운 해설

https://softeer.ai/practice/7727

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

생각이 한번 꼬여서 은근 애먹었는데,

이해하고나면 아? 생각보다 쉽네? 였다.

 

 

 

 

 

 

 

핵심 설명

변수 네이밍 규칙이 Worker와 Work로 하다보니 헷갈려서 바꿨다

Worker와 Gold로 바꾸고 일꾼이 골드를 수확한다고 생각하니 편했다.

 

각설하고,

맵 저장해주고~

여느때와 다름없이 dfs를 구현해준다.

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

            if( nx < 1 || ny < 1 || nx >= map.length || ny >= map[0].length ){
                continue;   // 맵 벗어난 경우
            }
            if(v[nx][ny] != 0){
                continue;
            }

            int nextGold = map[nx][ny];
            v[nx][ny] = 1;
            dfs(map, v, workerList, workerId, sum+nextGold, new Point(nx, ny),depth+1);
            v[nx][ny] = 0;
        }

맵 벗어난경우와, 기방문인 경우 continue;

백트래킹 v[][] = 1 -> 0 바꿔주기

뭐 별다른거 없다.

 

 

 

다만  depth==3 일때가 중요하다!!!!!!!!!! (제자리 첫수확 이후 3번의 수확이 끝난 시점)

체크1. 아래코드에서 return 꼭 넣으셔야 4번 수확하고 다음친구한테 넘어갑니다.

체크2. 아래코드에서 dfs넘기기전에 visit 검증 안하고 넘겨야 다음친구한테 넘어갑니다. (이미방문했더라도 중복 수확되어 어차피 최대값이 되지 않음)

        if(depth == 3){
            // System.out.println();
            if(workerId+1 < workerList.size()){
                v[workerList.get(workerId+1).x][workerList.get(workerId+1).y] = 1;
                int nextGold = map[workerList.get(workerId+1).x][workerList.get(workerId+1).y];
                dfs(map, v, workerList, workerId+1, sum+nextGold, new Point(workerList.get(workerId+1).x, workerList.get(workerId+1).y), 0);
            }
            return;
        }

1번째 인부(남우)가 dfs로 4칸의 골드를 다 수확한 시점이 될것이다.

이때부터는 이제 2번째 인부(친구중 한명)의 수확을 시작해야 한다.

 

workerId 라는 변수로 인부들의 인덱스 값을 모두 돌것이고,

다음에 dfs 돌려질 2번째 인부(친구중 한명)가 서있던 위치를 v=1 방문표시하고

sum+nextGold

를 수확해주면 된다.

 

 

 

 

 

 

 

 

 

 

가장 처음에 전체코드상 firstGold 를 수확했던 것처럼 말이다.

"dfs안에 dfs안에 dfs안에....엘리베이터 거울 속의 거울" 같은 느낌? 이랄까...

        int firstGold = map[workerList.get(0).x][workerList.get(0).y];
        map[workerList.get(0).x][workerList.get(0).y] = 0;
        v[workerList.get(0).x][workerList.get(0).y] = 1;
        dfs(map, v, workerList, 0, firstGold, new Point(workerList.get(0).x, workerList.get(0).y), 0);

 

 

 

 

2번째 인부도 dfs 다 돌려졌다면?

depth==3에 걸려서

3번째 인부가 dfs 돌려질것이다

 

그렇게 예시상

(26+185+80+80) 을 먼저 더해놓고

그다음

(25+88+99+50)이 더해지는거다.

 

 

 

 

 

 

 

전체 코드

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.

import java.io.*;
import java.util.*;

public class Main {

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

    public static class Point{
        int x;
        int y;

        public Point() {
        }

        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int map[][] = new int[n+1][n+1];
        int v[][] = new int[n+1][n+1];
        for(int i=1; i<n+1; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<n+1; j++){
                int k = Integer.parseInt(st.nextToken());
                map[i][j] = k;
                v[i][j] = 0;
            }
        }

        ArrayList<Point> workerList = new ArrayList<>();
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int inputX = Integer.parseInt(st.nextToken());
            int inputY = Integer.parseInt(st.nextToken());
            workerList.add(new Point(inputX, inputY));
        }

        int firstGold = map[workerList.get(0).x][workerList.get(0).y];
        map[workerList.get(0).x][workerList.get(0).y] = 0;
        v[workerList.get(0).x][workerList.get(0).y] = 1;
        dfs(map, v, workerList, 0, firstGold, new Point(workerList.get(0).x, workerList.get(0).y), 0);

        bw.write(String.valueOf( dap ) + "\n");
        bw.flush();
        bw.close();
    }

    public static void dfs(int[][] map, int[][] v, ArrayList<Point> workerList, int workerId, int sum, Point cur, int depth){

        dap = Math.max(dap, sum);

//        System.out.println();
//        for(int i=1; i< map.length; i++){
//            for(int j=1; j<map[0].length; j++){
//                if(i==cur.x && j==cur.y){
//                    System.out.print(sum + " ");
//                }
//                else{
//                    System.out.print("- ");
//                }
//            }
//            System.out.print(depth);
//            System.out.println();
//        }

        if(depth == 3){
            // System.out.println();
            if(workerId+1 < workerList.size()){
                v[workerList.get(workerId+1).x][workerList.get(workerId+1).y] = 1;
                int nextGold = map[workerList.get(workerId+1).x][workerList.get(workerId+1).y];
                dfs(map, v, workerList, workerId+1, sum+nextGold, new Point(workerList.get(workerId+1).x, workerList.get(workerId+1).y), 0);
            }
            return;
        }

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

            if( nx < 1 || ny < 1 || nx >= map.length || ny >= map[0].length ){
                continue;   // 맵 벗어난 경우
            }
            if(v[nx][ny] != 0){
                continue;
            }

            int nextGold = map[nx][ny];
            v[nx][ny] = 1;
            dfs(map, v, workerList, workerId, sum+nextGold, new Point(nx, ny),depth+1);
            v[nx][ny] = 0;
        }
    }

}