[백준] #9205 맥주 마시면서 걸어가기, BFS

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

 

시도 1

처음에 제출한 코드는 아래와 같다.

문제를 읽고 생각해보면서, 좌표와 좌표 사이의 거리가 1000 이하면 되는 문제네? 라고 생각하면

별도의 알고리즘 없이 구현하는 문제라고 생각했다.

여기서 내가 잘못 생각한 점은 주어진 편의점을 "순서대로" 방문하는 것이 아니라 방문 순서를 정할 수 있는데, 그 점을 놓쳤다.

또 아래 코드를 보니 굳이 시작, 편의점, 페스티벌 좌표를 나눌 필요없이 for문을 이용하면 되는데 불필요한 코드 분리가 있었던 게 보인다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        // 배열로 상황 만들기
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine()); // 맥주 파는 편의점 수
            st = new StringTokenizer(br.readLine(), " ");
            int[][] loc = new int[n + 2][2];
            loc[0] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                loc[j + 1] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            }

            st = new StringTokenizer(br.readLine(), " ");
            loc[n + 1] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};

            for (int j = 0; j < n + 1; j++) {
                int distance = (Math.abs(loc[j + 1][0] - loc[j][0]) + Math.abs(loc[j + 1][1] - loc[j][1]));
                if (distance > 1000) {
                    sb.append("sad").append("\n");
                    break;
                }

                if (j == n) {
                    sb.append("happy").append("\n");
                }
            }
        }

        System.out.println(sb);
    }
}

 

시도 2

아~ 편의점 방문 순서가 입력 순서가 아닌 것을 깨닫고, BFS를 생각하게 되었다.

해당 문제는 어떻게든 락 페스티벌에 도착하면 되는 것이기 때문에, 너비 우선 탐색을 이용하면 초반에 거를 수 있는 경로가 있을 것이라고 판단했다.

위에서 불필요하게 시작점, 편의점, 페스티벌 장소 코드를 분리했던 것을 한 번의 for문으로 입력 받았고, bfs을 이용해서 구현했다.

좌표로 visited 같은 배열을 만드는 것은 불필요하다고 생각해서 인덱스를 이용해 흐름을 설계했다.

또 중요한 점은 거리니까 절댓값을 해줘야 한다는 점..!

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

public class Main {
    static Deque<Integer> queue;
    static boolean[] visited;
    static int n;
    static int[][] loc;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        // 배열로 상황 만들기
        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine()); // 맥주 파는 편의점 수
            visited = new boolean[n + 2];
            loc = new int[n + 2][2];

            // loc 만들기
            for (int j = 0; j < n + 2; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                loc[j] = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            }

            String answer = bfs() ? "happy" : "sad";
            sb.append(answer).append("\n");
        }

        System.out.println(sb);
    }

    public static boolean bfs() {
        queue = new ArrayDeque<>();
        visited[0] = true;
        queue.offer(0);

        while (!queue.isEmpty()) {
            int newIndex = queue.poll();

            if (newIndex == n + 1) {
                return true;
            }

            for (int i = 1; i < n + 2; i++) {
                if (!visited[i]) {
                    int distance = Math.abs(loc[newIndex][0] - loc[i][0]) + Math.abs(loc[newIndex][1] - loc[i][1]);

                    if (distance <= 1000) {
                        visited[i] = true;
                        queue.offer(i);
                    }
                }
            }
        }

        return false;
    }
}