[백준] 9205번:맥주 마시면서 걸어가기 (Java 자바)

문제

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

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

 

풀이 및 소스코드

 

맥주를 마시면서 이동할 수 있는 거리는

50*20 = 1000 이다.

좌표들을 입력받고, 그 좌표들끼리 사이의 거리가 1000이하라면 서로 갈 수 있는 곳이기 때문에 정점을 양방향으로 연결해준다.

 

연결해준 정점을 토대로 집(g[0])부터 시작해서 bfs를 돌린다.

도착지 인덱스인 n+1에 도달하면 happy를, 도달하지 않는다면 sad를 출력해주면 된다.

 

 

 

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));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		
		for(int tt=0;tt<t;tt++) {
			int n = Integer.parseInt(br.readLine());
			
			node[] a = new node[n+2];
			//index : 0-집, 1~n-편의점, n+1-도착지
			for(int i=0;i<n+2;i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				a[i] = new node(x,y);
			}
			
			LinkedList<Integer>[] g = new LinkedList[n+2];
			for(int i=0;i<n+2;i++) {
				g[i] = new LinkedList<>();
			}
			for(int i=0;i<n+1;i++) {
				for(int j=i+1;j<n+2;j++) {
					if(Math.abs(a[i].x-a[j].x)+Math.abs(a[i].y-a[j].y)<=1000) {
						g[i].add(j);
						g[j].add(i);
					}
				}
			}
			//맥주를 마시면서 이동할 수 있는 거리 : 20*50 = 1000
            //이동할 수 있으면 연결해준다.
			
			boolean c = false;
			boolean[] v = new boolean[n+2];
            //연결된 것을 가지고 bfs 돌리기.
            //bfs 돌리다가 도착점까지 간다면 happy, 못간다면 sad
			Queue<Integer> q = new LinkedList<>();
			q.add(0);
			v[0] = true;
			while(!q.isEmpty()) {
				int now = q.poll();
				if(now==n+1) {
					c = true;
					break;
				}
				for(int i=0;i<g[now].size();i++) {
					if(!v[g[now].get(i)]) {
						v[g[now].get(i)] = true;
						q.add(g[now].get(i));
					}
				}
			}
			if(c) {
				sb.append("happy\n");
			}else {
				sb.append("sad\n");
			}
			
		}
		System.out.println(sb);
	}

}

class node {
	int x, y ;

	public node(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}
	
}