백준 23352 방탈출

접근 방식

브루트포스 방식으로 모든 지점에 대해서 BFS 탐색

시도한 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;
import java.util.Queue;
import java.util.StringTokenizer;

public class EscapeRoom {

    private static int[][] map;

    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {-1, 1, 0, 0};

    private static final List<Point> points = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        map = new int[n][];
        for (int i = 0; i < n; i++) {
            map[i] = Arrays.stream(br.readLine().trim().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
        }

        int answer = 0;
        for (int y = 0; y < map.length; y++) {
            for (int x = 0; x < map[0].length; x++) {
                if (map[y][x] == 0) {
                    continue;
                }
                answer = bruteforce(answer, x, y);
            }
        }
        System.out.print(answer);
    }

    private static int bruteforce(int answer, int x, int y) {
        Point maxDistancePoint = Point.Empty;
        for (int startY = 0; startY < map.length; startY++) {
            for (int startX = 0; startX < map[0].length; startX++) {
                if (map[startY][startX] == 0) {
                    continue;
                }
                points.add(dfs(new Point(startX, startY, 0), new Point(x, y, 0)));
            }
        }
        int tmp = sumRoomNum(new Point(x, y, 0), maxDistancePoint);
        if (answer < tmp) {
            answer = tmp;
        }
        return answer;
    }

    private static int sumRoomNum(Point lhs, Point rhs) {
        return map[lhs.getY()][lhs.getX()] + map[rhs.getY()][rhs.getX()];
    }

    private static Point dfs(Point start, Point goal) {
        boolean[][] visited = new boolean[map.length][map[0].length];
        Queue<Point> q = new ArrayDeque<>();
        visited[start.getY()][start.getX()] = true;
        q.offer(start);
        while (!q.isEmpty()) {
            Point cur = q.poll();
            if (goal.equals(cur)) {
                return cur;
            }
            for (int i = 0; i < 4; i++) {
                int _x = cur.getX() + dx[i];
                int _y = cur.getY() + dy[i];
                if (canMove(_x, _y) && !visited[_y][_x]) {
                    visited[_y][_x] = true;
                    q.offer(new Point(_x, _y, cur.getDistance() + 1));
                }
            }
        }
        return Point.Empty;
    }

    private static boolean canMove(int x, int y) {
        if (!(0 <= x && x < map[0].length && 0 <= y && y < map.length)) {
            return false;
        }
        return map[y][x] != 0;
    }

    private static class Point {

        public static Point Empty = new Point(0, 0, 0);

        private final int x;
        private final int y;
        private final int distance;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public int getDistance() {
            return distance;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}