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

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

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

 

bfs를 사용하여 해결 할 수 있는 문제이다!

맥주는 max 20개로 최대한 많이 갈 수 있는 거리는 1000이다.

편의점에 도착하면 맥주를 20개 다 리필 가능하기 때문에, 

현위치에서 1000까지의 거리 안에 갈 수 있는 편의점이 있는지 확인하고, 이미 간 적이 있는 곳이 아니라면 큐에 넣어서 현위치를 변경한다!

그렇게 현위치에서 축제까지의 거리가 1000이하라면 happy ~~~!

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for (int i = 0; i < t; i++) {
			int conv = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int sangX = Integer.parseInt(st.nextToken());
			int sangY = Integer.parseInt(st.nextToken());
			
            //편의점 정보
			int[][] convArr = new int[conv][2];
			for (int j = 0; j < conv; j++) {
				st = new StringTokenizer(br.readLine());
				convArr[j][0] = Integer.parseInt(st.nextToken());
				convArr[j][1] = Integer.parseInt(st.nextToken());
			}

			//축제 정보
			st = new StringTokenizer(br.readLine());
			int festivalX = Integer.parseInt(st.nextToken());
			int festivalY = Integer.parseInt(st.nextToken());

 			//편의점 방문 정보
			boolean[] visited = new boolean[conv];
			Queue<int[]> q = new LinkedList<>();
			q.add(new int[] { sangX, sangY }); //첫 위치 넣음
			boolean result = false;
			while (!q.isEmpty()) {
				int[] temp = q.poll();
				if (Math.abs(festivalX - temp[0]) + Math.abs(festivalY - temp[1]) <= 1000) {
					result=true;
				}
				//현위치에서 편의점 거리 확인
				for (int j = 0; j < conv; j++) {
					if (Math.abs(convArr[j][0] - temp[0]) + Math.abs(convArr[j][1] - temp[1]) <= 1000&&!visited[j]) {
						q.add(new int[] {convArr[j][0],convArr[j][1]});
						visited[j]=true;
					}
				}
			}

			if(!result)
				System.out.println("sad");
			else 
				System.out.println("happy");

		}

	}

}