9205. 맥주 마시면서 걸어가기

문제 개요

N+2개의 노드를 가지는 가중치 그래프가 있을 때, 처음 번호의 노드부터 마지막 번호의 노드까지 도달 가능한지를 확인해야 합니다.

문제 접근

어떤 노드에서 특정 노드까지 도달할 수 있는지 확인하는 방법은 DFS 혹은 BFS를 이용하면 구할 수 있습니다.

따라서 N+2개의 노드들에 대한 거리를 구하고 이를 가중치로 가지는 그래프를 만들어 DFS를 통해 정답을 구할 수 있었습니다.

public class Main {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    static int t;
    static int[] n = new int[55];
    static int[][][] positions = new int[55][105][];
    static final int MOVEMENT = 50;

    private static String[] readLines() throws IOException {
        String[] lines = new String[5500];
        lines[0] = bf.readLine();
        int count = Integer.parseInt(lines[0]);
        for(int i=0, row=1;i<count;i++){
            lines[row] = bf.readLine();
            int storeCount = Integer.parseInt(lines[row]);
            for(int j=0;j<storeCount+2;j++){
                lines[row+1+j] = bf.readLine();
            }
            row += storeCount+3;
        }
        return lines;
    }

    private static int[] parseString(String position) {
        return Arrays.stream(position.split(" ")).mapToInt(Integer::parseInt).toArray();
    }

    public static void input(String[] lines) {
        t = Integer.parseInt(lines[0]);
        for (int i = 0, row = 1; i < t; i++) {
            n[i] = Integer.parseInt(lines[row]);
            for (int j = 0; j < n[i] + 2; j++) {
                positions[i][j] = parseString(lines[row + 1 + j]);
            }
            row += n[i] + 3;
        }
    }

    private static int[][] calcDistances(int t, int n) {
        int[][] distances = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                distances[i][j] = distances [j][i] = Math.abs(positions[t][i][0] - positions[t][j][0])
                        + Math.abs(positions[t][i][1] - positions[t][j][1]);
            }
        }

        return distances;
    }

    private static boolean dfs(int t, int n, int[][] distances){
        int cur = 0;
        int beer = 20;
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[n];
        stack.push(cur);
        visited[cur] = true;

        while(!stack.isEmpty()){
            cur = stack.pop();
            if(cur == n-1){
                return true;
            }
            for(int i=0;i<n;i++){
                if(!visited[i] && (distances[cur][i] <= beer * MOVEMENT)){
                    stack.push(i);
                    visited[i] = true;
                }
            }
        }

        return false;
    }

    public static String process() {
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < t; i++) {
            if(dfs(i, n[i]+2, calcDistances(i, n[i]+2))){
                result.append("happy\n");
                continue;
            }
            result.append("sad\n");
        }

        return result.toString();
    }

    public static void main(String[] args) throws IOException {
        input(readLines());
        System.out.println(process());
    }
}

문제: https://www.acmicpc.net/problem/9205