백준 9205 맥주 마시면서 걸어가기 (Java)

1. 문제 링크

 

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 시작점과 끝점이 정해져 있어 좌표 기준으로 BFS를 진행했다..
2. 시작점을 큐에 넣고 큐가 빌 때까지 탐색한다.
3. 편의점과 현재 위치를 전부 비교하면서 맥주 20병으로 갈 수 있는 거리(1,000) 이내인지 확인하면서 큐에 넣고 방문 처리를 한다.
4. 페스티벌 위치에 도착하면 happy를 출력한다. 끝까지 도착하지 못한다면 sad를 출력한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		String[] split = new String[2];
		for(int t=0;t<T;t++) {
			String result = "sad";
			int n = Integer.parseInt(br.readLine());
			Point[] point = new Point[n+2];
			boolean[] visit = new boolean[n+2];
		
			for(int i=0;i<n+2;i++) {
				split = br.readLine().split(" ");
				point[i] = new Point(Integer.parseInt(split[0]), Integer.parseInt(split[1])); 
			}
			
			Queue<Point> queue = new ArrayDeque<>();
			queue.offer(point[0]);
			visit[0] = true;
			
			Point now;
			while(!queue.isEmpty()) {
				now = queue.poll();				
				for(int i=1;i<n+2;i++) {
					if(visit[i]) continue;
					int dis = Math.abs(now.x-point[i].x)+Math.abs(now.y-point[i].y);
					if(dis<=1000) {
						if(i==n+1) {
							result = "happy";
							break;
						}
						queue.offer(point[i]);
						visit[i] = true;
					}
				}
			}
			sb.append(result).append("\n");
		}
		System.out.println(sb);
	}
}