[BOJ] 9205번 맥주 마시면서 걸어가기

링크

9205

풀이

• 도착지 기준 1000m전에 편의점이 있어야한다.
• bfs탐색: 현재 위치에서 갈 수있는 편의점들을 모두 큐에 넣으면서 탐색한다.

코드

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

public class Main_9205_맥주마시면서걸어가기 {
	private static ArrayList<int[]>  conveniences;
	private static int sx, sy, dx, dy, n;
	private static Queue<int[]>  q;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc = 1; tc <= T; tc++) {
			n = Integer.parseInt(br.readLine());
			conveniences = new ArrayList<>();
			q = new LinkedList<>();
			for(int i = 0; i <n+2; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				if(i == 0) {
					sx = Integer.parseInt(st.nextToken());
					sy = Integer.parseInt(st.nextToken());
					q.add(new int[] {sx, sy});
				}else if(i == n+1) {
					dx = Integer.parseInt(st.nextToken());
					dy = Integer.parseInt(st.nextToken());
				}else {
					int x = Integer.parseInt(st.nextToken());
					int y = Integer.parseInt(st.nextToken());
					conveniences.add(new int[] {x, y});
				}
			}// end of 입력
			
			System.out.println(bfs()? "happy" : "sad");
		}//end of tc 
	}

	private static boolean bfs() {
		boolean[] vis = new boolean[n]; //편의점 방문 체크
		while(!q.isEmpty()) {
			int[] cur = q.poll();
			int x = cur[0];
			int y = cur[1];
			int dis = distance(x, y, dx, dy);
			if(dis <= 1000) {
				return true;
			}
			for(int i = 0; i < n; i++) {
				if(!vis[i]) {
					int nx = conveniences.get(i)[0];
					int ny = conveniences.get(i)[1];
					if(distance(nx, ny, x, y) <= 1000) {
						vis[i] = true;
						q.add(new int[] {nx, ny});
					}
				}
			}

		}
		return false;
	}

	private static int distance(int x, int y, int dx, int dy) {
		return Math.abs(x - dx) + Math.abs(y - dy);
	}

}