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

문제

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

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

 

풀이

BFS 또는 플로이드 와샬을 이용하여 풀 수 있다.

플로이드 와샬로 풀 경우에는 시작정점과 도착정점의 연결여부로 풀 수 있다.

코드

BFS

import java.util.*;
import java.io.*;

public class Main {

	static class Point{
		int x;
		int y;
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
	}
	
	static int sx, sy, dx, dy;
	static ArrayList<Point> arr;
	static StringBuilder sb = new StringBuilder();
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int t = Integer.parseInt(br.readLine());
		
		for(int task = 0; task < t; task++) {
			int n = Integer.parseInt(br.readLine());
		
			arr = new ArrayList<>();
			
			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());
				
				arr.add(new Point(x, y));
				
				if(i==0) {
					sx = x;
					sy = y;
				}
				if(i==n+1) {
					dx = x;
					dy = y;
				}
			}
			
			bfs();

		}
		System.out.println(sb);
	}		
	
	
	static void bfs() {
		Queue<Point> que = new LinkedList<>();
		boolean check [] = new boolean [arr.size()];
		
		que.add(new Point(sx, sy));
		check[0] = true;	

		while(!que.isEmpty()) {
			Point cur = que.poll();
			
			if(cur.x == dx && cur.y == dy) {
				sb.append("happy\n");
				return;
			}		
			
			for(int i=1;i<arr.size();i++) {
				if(check[i]) continue;
				
				Point next = arr.get(i);
				int nx = Math.abs(next.x - cur.x);
				int ny = Math.abs(next.y - cur.y);

				if(nx + ny <= 1000) {
					que.add(new Point(next.x, next.y));
					check[i] = true;
				}
			}
			
		}
		sb.append("sad\n");
		return;
		
	}
}

플로이드 와샬

import java.util.*;
import java.io.*;

public class Main {

	static class Point{
		int x;
		int y;
		
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		
	}
	
	
	public static void main (String[] args) throws java.lang.Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		
		for(int task = 0; task < t; task++) {
			int n = Integer.parseInt(br.readLine());
		
			ArrayList<Point> arr = new ArrayList<>();
			boolean check [][] = new boolean[n+2][n+2];
			
			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());
				
				arr.add(new Point(x, y));
				
			}
			
			//두 정점이 1000m 이하면 check를 true로
			for(int i=0;i<n+2;i++) {
				for(int j=0;j<n+2;j++) {
					Point cur = arr.get(i);
					Point next = arr.get(j);
					if((Math.abs(cur.x - next.x) + Math.abs(cur.y - next.y)) <= 1000)
						check[i][j] = true;
				}
			}
			
			//플로이드 와샬. i->j로 갈때 i->k 로 갈 수있고 k->j 로 갈 수 있으면 i->j로도 갈 수 있다.
			//경유는 무조건 맨 바깥쪽 for문으로 
			for(int k=0;k<n+2;k++) {
				for(int i=0;i<n+2;i++) {
					for(int j=0;j<n+2;j++) {
						if(check[i][k] && check[k][j])
							check[i][j] = true;
					}
				}
			}
			
			if(check[0][n+1])
				sb.append("happy\n");
			else
				sb.append("sad\n");

		}
		System.out.println(sb);
	}		
	
}