[백준] 9205 맥주 마시면서 걸어가기 (JAVA)

✉️문제

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

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

 

📝 접근

   DFS와 BFS의 경계가 모호한 문제인 것 같다. 개인적으로 Queue를 이용하는 것 보다는 DFS가 좋아 DFS를 이용하여 풀이하였다.

 

🗝 문제풀이

1. 첫 입력으로 테스트 개수가 주어진다. 따라서 테스트 개수를 이용한 for문을 돈다. 

2. 편의점의 수가 주어지는데, 이 좌표들을 store 배열에 저장하였다. 

3. 편의점을 방문했는지 체크하기 위해 visited 배열을 초기화 한 다음에 solution (DFS) 함수를 호출한다. 

int t = sc.nextInt(); // 테스트 개수
for(int i = 0; i < t; i++) {
    flag = false;
    int n = sc.nextInt(); // 편의점 수
    store = new Point[n];
    sangen = new Point(sc.nextInt(), sc.nextInt()); // 상근이 좌표
    for(int j = 0; j < n; j++) {
        store[j] = new Point(sc.nextInt(), sc.nextInt());
    }
    festival = new Point(sc.nextInt(), sc.nextInt());
    
    visited = new boolean[n];
    solution(sangen.x, sangen.y);

    if(flag) System.out.println("happy");
    else System.out.println("sad");
}

 

4. 현재 좌표와 목적지(festival) 좌표의 거리 계산이 DISTANCE(20 * 50)안에 있으면 목적지에 갈 수 있으므로 flag를 true로 변경한다.

5. 만약 4번의 조건이 성립이 안되고 편의점에는 갈 수 있다면 편의점의 좌표를 표시하고 편의점 위치로 DFS를 다시 진행한다.

6. 4번과 5번을 반복한다.

public static void solution(int curX, int curY) {
    if(flag) return;

    if(Math.abs(curX - festival.x) + Math.abs(curY - festival.y) <= 20 * 50) {
        flag = true;
        return;
    }

    // 편의점
    for(int i = 0; i < store.length; i++) {
        if(visited[i]) continue;

        if(Math.abs(curX - store[i].x) + Math.abs(curY - store[i].y) > DISTANCE) continue;

        visited[i] = true;
        solution(store[i].x, store[i].y);
    }
}

 

[최종코드]

package baekjoon;

import java.util.Scanner;

public class B9205 {

    static Point sangen, festival;
    static Point[] store;
    static final int DISTANCE = 20 * 50;
    static boolean flag = false;
    static boolean[] visited;

    static class Point {
        int x, y;

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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt(); // 테스트 개수
        for(int i = 0; i < t; i++) {
            flag = false;
            int n = sc.nextInt(); // 편의점 수
            store = new Point[n];
            sangen = new Point(sc.nextInt(), sc.nextInt()); // 상근이 좌표
            for(int j = 0; j < n; j++) {
                store[j] = new Point(sc.nextInt(), sc.nextInt());
            }
            festival = new Point(sc.nextInt(), sc.nextInt());

            visited = new boolean[n];
            solution(sangen.x, sangen.y);

            if(flag) System.out.println("happy");
            else System.out.println("sad");
        }
    }

    public static void solution(int curX, int curY) {
        if(flag) return;

        if(Math.abs(curX - festival.x) + Math.abs(curY - festival.y) <= DISTANCE) {
            flag = true;
            return;
        }

        // 편의점
        for(int i = 0; i < store.length; i++) {
            if(visited[i]) continue;

            if(Math.abs(curX - store[i].x) + Math.abs(curY - store[i].y) > DISTANCE) continue;

            visited[i] = true;
            solution(store[i].x, store[i].y);
        }
    }
}