[BOJ] 백준 9205 - 맥주 마시면서 걸어가기 (자바)

BFS..

예제가 몇개 없어서 헤맨 문제.. 라기보단 문제 접근 자체를 완전 이상하게 접근함.

편의점의 위치가 출발점에서 가까운 순서대로 위치한 줄 알았는데그게 아님.

결국 편의점 위치를 일일히 확인해 봐야한다.

풀이

1. 시작위치(상근이네), 편의점 위치, 도착위치(페스티벌) 의 좌표 모두 하나의 클래스 배열 location[] 안에 넣어준다.

2. 시작위치로 부터 출발한다. (큐에 넣어준다.)

3. 출발하여 location[] 클래스 배열안에 있는 조건에 맞는 좌표를 방문한다.

4. 조건이란 출발위치로부터 다음 위치의 차이가 1000이하이며, 이전에 방문하지 않은 점이여야한다.

5. 페스티벌 위치와 계속 비교해주며 페스티벌 위치라면 그 즉시 성공깃발(boolean success) 만 바꾸고 종료한다.

6 성공깃발 여부에 따라 출력해주면 된다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int Testcase = Integer.parseInt(br.readLine());
 
        for (int t = 0; t < Testcase; t++) {
            int N = Integer.parseInt(br.readLine());
            LOCATION[] location = new LOCATION[N + 2];
            int[] check = new int[N + 2];
            Queue<LOCATION> q = new LinkedList<LOCATION>();
            boolean success = false;
            String[] str;
            for (int i = 0; i < N + 2; i++) {
                str = br.readLine().split(" ");
                location[i] = new LOCATION(Integer.parseInt(str[0]), Integer.parseInt(str[1]));
            }
            //--------------입력 끝--------------//
            
            LOCATION start = location[0];    //시작 위치
            LOCATION end = location[N + 1];    //도착 위치
            q.add(start);    //시작 위치로 부터 출발
            
            while (!q.isEmpty()) {
                LOCATION current = q.poll();
                //만약 다음에 접근할 위치가 도착 위치라면 성공깃발만 바꾸고 종료한다.
                if(current.equals(end)){
                    success = true;
                    break;
                }
                //모든 방문할 위치 중에서 거리가 1000(맥주 20병) 안에 도착 할때만 Queue에 저장한다.
                for (int i = 1; i < N + 2; i++) {
                    if (check[i] == 0 &&Math.abs(current.x - location[i].x) + Math.abs(current.y - location[i].y) <= 1000) {
                        q.add(location[i]);
                        check[i] = 1;    //왔던 위치 다시 방문 하지 않기 위해서 만들어줌
                    }
                }
            }
            if(success){
                System.out.println("happy");
            }
            else{
                System.out.println("sad");
            }
        }
    }
}
 
class LOCATION {
    int x;
    int y;
 
    LOCATION(int x, int y) {
        this.x = x;
        this.y = y;
    }
}