[Algorithm] 백준 9205 (bfs 완전탐색, floyd-warshall)

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

9205번: 맥주 마시면서 걸어가기

 

틀렸던 이유

처음에 그리디하게 경로 탐색을 해서 틀렸다. (현재 위치에서 제일 가까운 점으로 이동 or 도착점까지 거리가 제일 짧아지는 방향으로 이동) 하지만 이 문제는 그리디하게 풀면 안되는 문제다!

 

1. 완전 탐색 (bfs)

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        // 5:03
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            String answer = solution();
            bw.write(answer+"\n");
        }
        bw.flush();
    }

    private static String solution() throws IOException {
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int s1 = Integer.parseInt(st.nextToken()) + 32768;
        int s2 = Integer.parseInt(st.nextToken()) + 32768;
        Node start = new Node(s1, s2);
        int MOVE = 20 * 50;

        Node[] mid = new Node[n];
        int[] visit = new int[n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) + 32768;
            int c = Integer.parseInt(st.nextToken()) + 32768;

            mid[i] = new Node(r, c);
        }

        st = new StringTokenizer(br.readLine());

        int e1 = Integer.parseInt(st.nextToken()) + 32768;
        int e2 = Integer.parseInt(st.nextToken()) + 32768;
        Node end = new Node(e1, e2);

        Queue<Node> q = new LinkedList<>();
        q.offer(start);

        while(!q.isEmpty()) {
            Node poll = q.poll();
//            System.out.println("poll = " + poll);

            if(calculate(poll, end) <= MOVE) return "happy";

            for(int i = 0; i < n; i++) {
                if(visit[i] == 1) continue;

                if(calculate(poll, mid[i]) <= MOVE) {
                    visit[i] = 1;
                    q.offer(mid[i]);
                }
            }
        }
        return "sad";
    }

    private static int calculate(Node n1, Node n2) {
        return Math.abs(n1.r - n2.r) + Math.abs(n1.c - n2.c);
    }

    private static class Node {
        int r;
        int c;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return r == node.r && c == node.c;
        }

        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "r=" + r +
                    ", c=" + c +
                    '}';
        }

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

2. floyd-warshall

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        // 5:03
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());

        while(T-- > 0) {
            String answer = solution();
            bw.write(answer+"\n");
        }
        bw.flush();
    }

    private static String solution() throws IOException {
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int s1 = Integer.parseInt(st.nextToken()) + 32768;
        int s2 = Integer.parseInt(st.nextToken()) + 32768;
        Node start = new Node(s1, s2);
        int MOVE = 20 * 50;

        Node[] map = new Node[n+2];

        map[0] = start;
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) + 32768;
            int c = Integer.parseInt(st.nextToken()) + 32768;

            map[i+1] = new Node(r, c);
        }

        st = new StringTokenizer(br.readLine());

        int e1 = Integer.parseInt(st.nextToken()) + 32768;
        int e2 = Integer.parseInt(st.nextToken()) + 32768;
        Node end = new Node(e1, e2);
        map[n+1] = end;

        int[][] isMovable = new int[n+2][n+2];
        // init
        for(int i = 0; i < n+2; i++) {
            for(int j = 0; j < n+2; j++) {
                if(calculate(map[i], map[j]) <= MOVE) {
                    isMovable[i][j] = 1;
                }
            }
        }

        // floyd-warshall
        for(int k = 0; k < n+2; k++) {
            for(int i = 0; i < n+2; i++) {
                for(int j = 0; j < n+2; j++) {
                    if(isMovable[i][k] == 1 && isMovable[k][j] == 1) {
                        isMovable[i][j] = 1;
                    }
                }
            }
        }

        return isMovable[0][n+1] == 1 ? "happy" : "sad";
    }

    private static void print(int[][] arr) {
        for(int i = 0; i < arr.length; i++) {
            for(int j = 0; j < arr[0].length; j++) {
                if(arr[i][j] == 1000000) System.out.print(String.format("%3d", -1));
                else System.out.print(String.format("%10d", arr[i][j]));
            }
            System.out.println();
        }
    }

    private static int calculate(Node n1, Node n2) {
        return Math.abs(n1.r - n2.r) + Math.abs(n1.c - n2.c);
    }

    private static class Node {
        int r;
        int c;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return r == node.r && c == node.c;
        }

        @Override
        public int hashCode() {
            return Objects.hash(r, c);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "r=" + r +
                    ", c=" + c +
                    '}';
        }

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

        // init
        for(int i = 0; i < n+2; i++) {
            for(int j = 0; j < n+2; j++) {
                if(calculate(map[i], map[j]) <= MOVE) {
                    isMovable[i][j] = 1;
                }
            }
        }

        // floyd-warshall
        for(int k = 0; k < n+2; k++) {
            for(int i = 0; i < n+2; i++) {
                for(int j = 0; j < n+2; j++) {
                    if(isMovable[i][k] == 1 && isMovable[k][j] == 1) {
                        isMovable[i][j] = 1;
                    }
                }
            }
        }

여기서 주의할 점은 양방향 표시!

for 문에서 j = i+1 이 아니라 j= 0 을 시작점으로 했다는 것은 i -> j , j -> i 모두 고려한다는 것이다.

 

오늘의 교훈
1. 그래프 문제는 양방향인지 단방향인지 고려해야한다.
2. 최단거리라고 한 적 없다! 그리디하게 하는건 많은 고려가 필요하다.