[백준] 9205번 : 맥주 마시면서 걸어가기 - 자바[Java]

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

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

풀이

맥주 한 박스에는 맥주가 20개 들어있으며 50미터에 한 병씩 마시기 때문에 최대 1000m를 갈 수 있다.

즉, 처음 출발할 때와 편의점에 들렀을 때 최대 1000m를 갈 수 있다.

처음 출발할 때 1000m 이내로 아직 가지 않은 편의점이 있다면 그 편의점으로 가고, 이 과정을 반복해서 페스티벌 장소에 도착할 수 있다면 happy를 출력하고, 갈 수 없다면 sad를 출력하면 된다.

 

DFS로 풀려고 했지만 시간초과가 떴기 때문에, BFS로 풀어서 문제를 해결했다.

DFS/BFS 분기가 편의점을 방문하는지이므로 DFS를 수행하면 같은 편의점을 여러번 방문하는 등 불필요한 탐색이 발생하기 때문에 시간초과가 뜬다.

로직

1. 좌표 정보를 저장하는 static class Position을 선언한다.

2. 테스트 케이스 개수를 입력받는다.

3. 편의점 개수 n, 집 좌표, 편의점 좌표(n개), 페스티벌 좌표를 입력받는다. 이 때 편의점 좌표는 ArrayList<Postion> list에 저장한다.

4. BFS를 수행하는 beer() 함수를 호출하여 true를 리턴하면 happy를 출력하고, false를 리턴하면 sad를 출력한다.

 

boolean beer(ArrayList<Position> list, Position festival, Position house) : BFS를 수행하여 집에서 출발하여 페스티벌에 도착할 수 있으면 true, 도착할 수 없으면 false를 리턴한다.

public static boolean beer(ArrayList<Position> list, Position festival, Position house) {

        //편의점의 방문 여부 체크
        boolean[] visited = new boolean[list.size()];

        Queue<Position> q = new LinkedList<>();
        q.add(house);

        while(!q.isEmpty()) {
            Position cur = q.poll();
            if (Math.abs(festival.x - cur.x)+ Math.abs(festival.y - cur.y)<= 1000) {
                return true;
            }

            for (int i = 0; i < list.size(); i++) {
                if (!visited[i]) {
                    Position tmp = list.get(i);
                    if (Math.abs(tmp.x - cur.x)+ Math.abs(tmp.y - cur.y)<= 1000) {
                        visited[i] = true;
                        q.add(new Position(tmp.x, tmp.y));
                    }
                }
            }
        }

        return false;
    }

• 편의점을 방문했는지 체크하기 위한 방문 배열 visited을 선언한다. i번째 편의점을 방문했으면 visited[i] = true, 방문하지 않았으면 visited[i] = false 이다.
• 처음에 큐에 집 좌표를 추가한다.
• BFS를 수행한다.
  • 큐에서 좌표 하나를 꺼낸다.
  • 현재 좌표에서 페스티벌 장소까지 1000m 이하라면 true를 리턴한다.
  • 아직 방문하지 않은 편의점을 찾고, 그 편의점들 중에서 현재 좌표에서 1000m 이하라면 큐에 그 편의점 좌표를 추가한다.
• BFS가 끝났는데도 true를 리턴하지 못했다면 페스티벌 장소로 갈 수 없으므로 false를 리턴한다.

 

코드

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

public class Main {

    static class Position {
        int x, y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        while (t-- >0 ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            Position house = new Position(x, y);

            ArrayList<Position> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                x = Integer.parseInt(st.nextToken());
                y = Integer.parseInt(st.nextToken());
                list.add(new Position(x, y));
            }

            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            Position festival = new Position(x, y);

            if (beer(list, festival, house))
                bw.write("happy\n");
            else bw.write("sad\n");

        }

        bw.flush();
        bw.close();
        br.close();

    }

    public static boolean beer(ArrayList<Position> list, Position festival, Position house) {

        //편의점의 방문 여부 체크
        boolean[] visited = new boolean[list.size()];

        Queue<Position> q = new LinkedList<>();
        q.add(house);

        while(!q.isEmpty()) {
            Position cur = q.poll();
            if (Math.abs(festival.x - cur.x)+ Math.abs(festival.y - cur.y)<= 1000) {
                return true;
            }

            for (int i = 0; i < list.size(); i++) {
                if (!visited[i]) {
                    Position tmp = list.get(i);
                    if (Math.abs(tmp.x - cur.x)+ Math.abs(tmp.y - cur.y)<= 1000) {
                        visited[i] = true;
                        q.add(new Position(tmp.x, tmp.y));
                    }
                }
            }
        }

        return false;
    }
}

 

---

DFS로 수행하여 시간초과가 난 코드

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

public class Main {

    static class Position {
        int x, y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static boolean flag = false;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());

        while (t-- >0 ) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            Position house = new Position(x, y);

            ArrayList<Position> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                x = Integer.parseInt(st.nextToken());
                y = Integer.parseInt(st.nextToken());
                list.add(new Position(x, y));
            }

            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            Position festival = new Position(x, y);

            flag = false;
            boolean[] visited = new boolean[n];
            beer(list, festival, visited, house.x, house.y);

            if (flag)
                bw.write("happy\n");
            else bw.write("sad\n");

        }

        bw.flush();
        bw.close();
        br.close();

    }

    public static void beer(ArrayList<Position> list, Position festival, boolean[] visited, int x, int y) {
        if (Math.abs(festival.x - x)+ Math.abs(festival.y - y)<= 1000) {
            flag = true;
            return;
        }
        if (flag) return;

        for (int i = 0; i < list.size(); i++) {
            if (!visited[i]) {
                Position tmp = list.get(i);
                if (Math.abs(tmp.x - x)+ Math.abs(tmp.y - y)<= 1000) {
                    visited[i] = true;
                    beer(list, festival, visited, tmp.x, tmp.y);
                    visited[i] = false;
                }
            }
        }
    }
}