[java] 백준 9205 : 맥주 마시면서 걸어가기

문제

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

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

 

풀이

package main;
import java.io.*;
import java.util.*;

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

public class Main {
	static boolean[] visited;
	static ArrayList<Point> p;
	static int n;
	static ArrayList<Integer>[] graph;
	
	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int t = Integer.parseInt(br.readLine()); 
	
		for(int i=0; i<t; i++) {
			n = Integer.parseInt(br.readLine()); 
			 
			p = new ArrayList<Point>();
			
			
			for(int j=0; j<n+2; j++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				p.add(new Point(x,y));
				
			}
			
			graph = new ArrayList[p.size()];
			visited= new boolean[p.size()];
			for(int k=0; k<p.size(); k++) {
				graph[k]= new ArrayList<>();
			}
			
			for(int s=0; s< p.size(); s++) {
				for(int e=s+1; e<p.size(); e++) {
					Point a = p.get(s);
					Point b = p.get(e);
					if(Math.abs(a.x - b.x) + Math.abs(a.y - b.y)<=1000) {
						graph[s].add(e);
						graph[e].add(s);
					}
				}
				
			}
			
		
			if(BFS()) {
				System.out.println("happy");
			}else {
				System.out.println("sad");
			}
			
		
			
		}
	
	
		
		
	}
	
	static boolean BFS() {
		Queue<Integer> q = new LinkedList<>();
		q.add(0);
		visited[0] = true;
		
		while(!q.isEmpty()) {
		
			int now = q.poll();
			if( now == p.size()-1) return true;
			for(int next : graph[now]) {
				if(!visited[next]) {
					visited[next]=true;
					q.add(next);
				}
			}
			
		}
		
		return false;
	}

	
	}

 

맥주 한병에 50m 갈 수 있으므로 50 * 20 = 1000m 이내이면 어디든 가능하다 

시작점, 편의점, 도착점을 정점이라고 생각하고 각 정점사이의 거리를 계산하여 1000이하이면 간선으로 연결하는 그래프를 만들어준다.

그 그래프를 bfs를 이용하여 도착지점까지 갔는지 확인하는 식으로 풀이한다.