함께하는 효도

사용 알고리즘: dfs, bfs

사용 언어: java

 

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

public class Main {
    static int n,m,map[][],friends[][], answer;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) {
        init();

        boolean[][] visit = new boolean[n][n];
        for(int i=0; i<m; i++) {
            visit[friends[i][0]][friends[i][1]] = true;
        } //시작점은 방문 처리

        dfs(0, visit); //num번째 친구, 수확량더해야하는-, 처음 합계

        System.out.println(answer);
    }

    static void dfs(int num, boolean[][] visit) {
        if(num == m) {
            int sum = 0;
            
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(visit[i][j]) sum += map[i][j];
                }
            }
            
            answer = Math.max(answer, sum);
            return;
        }

        Queue<Work> q = new ArrayDeque<>();
        q.add(new Work(new int[] {friends[num][0], friends[num][1]}, visit, 0));

        while(!q.isEmpty()) {
            Work work = q.poll();
            int x = work.point[0];
            int y = work.point[1];
            boolean[][] visited = work.visit;
            int move = work.move;

            if(move > 2) {
                dfs(num + 1, visited);
                continue;
            }

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

                if(nx>=0&&nx<n && ny>=0&&ny<n) {
                    if(!visited[nx][ny]) {
                        boolean[][] visit2 = copyVisit(visited);
                        visit2[nx][ny] = true;
                        q.add(new Work(new int[] {nx, ny}, visit2, move + 1));
                    }
                }
            }
        }
    }

    static boolean[][] copyVisit(boolean[][] visit) {
        boolean[][] visit2 = new boolean[n][n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                visit2[i][j] = visit[i][j];
            }
        }
        return visit2;
    }
    
    static void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); //맵의 크기
        m = sc.nextInt(); //친구 수

        map = new int[n][n];
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                map[i][j] = sc.nextInt(); //열매열매
            }
        }
        //

        friends = new int[m][2];
        for(int i=0; i<m; i++) {
            friends[i][0] = sc.nextInt() - 1;
            friends[i][1] = sc.nextInt() - 1;
        }
    }
}

class Work {
    int[] point;
    boolean[][] visit;
    int move;

    public Work(int[] point, boolean[][] visit, int move) {
        this.point = point;
        this.visit = visit;
        this.move = move;
    }
}

 

키야~~

dfs에 bfs를 섞을 생각은 우째 했으까

 

dfs만 쓰려다가 메모리 초과 날 거 같아서 머리 좀 써봤다 이거야