#백준_9205 맥주 마시면서 걸어가기 - Java 자바

# 유형 : 그래프 , BFS, DFS ,플로이드와샬

# 두 가지 방법으로 풀었다. 첫 번째는  플로이드 와샬 방법, 그리고 두 번째 방법은 평소 많이 사용하던 BFS로 풀었다. 

플로이드 와샬 방법으로는 집(출발지) 편의점(거쳐가는 정점) 락 페스티벌(도착점)으로 잡고 알고리즘을 사용하면 된다.

BFS는 인접 리스틀 사용하여 BFS 알고리즘을 완성하면 된다. 꼭 한 방법으로만 푸는게 아니고 여러 방법으로 푸는 것도 알고리즘 실력에도 향상이 되니 여러 방법을 접하고 도전해보는 것을 추천한다.

 

1) 플로이드 와샬을 이용한 풀이

package bj;
 
import java.awt.Point;
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 p9205_floyd {
    static int N;    
    static int arr[][];
    static ArrayList<Point> arrList;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            N = Integer.parseInt(br.readLine());
            
            arrList = new ArrayList<>();
            arr = new int[N+2][N+2];
            for(int i=0; i<N+2; i++)
                for(int j=0; j<N+2; j++)
                    arr[i][j]=999999;
            
            StringTokenizer st;
            
            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());
                
                arrList.add(new Point(x,y));
            }
            
            for(int i=0; i<N+2; i++) {
                for(int j=0; j<N+2; j++) {
                    if(i==j)
                        continue;
                    
                    Point current = arrList.get(i);
                    Point next = arrList.get(j);
                    
                    int dist = Math.abs(current.x-next.x)+Math.abs(current.y-next.y);
                    if(dist<=1000)
                        arr[i][j] = 1;
                }
            }
            floyd_warshall();
            if(0<arr[0][N+1] && arr[0][N+1]<999999)
                System.out.println("happy");
            else
                System.out.println("sad");
        }
    }
    public static void floyd_warshall() {
        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(arr[i][j] > arr[i][k] + arr[k][j])
                        arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
    }
    
}
 

2) BFS를 이용한 풀이

package bj;
 
import java.awt.Point;
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 p9205 {
    static int N;    
//    static int arr[][];
    static Point arr[];
    static boolean visit[];
    static ArrayList<Integer> arrList[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        for(int tc=0; tc<testCases; tc++) {
            N = Integer.parseInt(br.readLine());
            
            arrList = new ArrayList[N+2];
            visit = new boolean[N+2];
            for(int i=0; i<N+2; i++)
                arrList[i] = new ArrayList<>();
            
            arr = new Point[N+2];
            
            StringTokenizer st;
            
            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[i] = new Point(x,y);
            }
            
            for(int i=0; i<N+1; i++) {
                for(int j=i+1; j<N+2; j++) {
                    float dist = (float) ((Math.abs(arr[i].x - arr[j].x) + Math.abs(arr[i].y -arr[j].y))/50.0);
                    if(dist <= 20) {
                        arrList[i].add(j);
                        arrList[j].add(i);
                    }
                }
            }
            
            if(bfs())
                System.out.println("happy");
            else
                System.out.println("sad");
            
        }
    }
    private static boolean bfs() {
        // TODO Auto-generated method stub
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visit[0] = true;
        
        while(!queue.isEmpty()) {
            int index =queue.poll();
//            System.out.println(index);
            if(index == N+1)
                return true;
            
            for(int i=0; i<arrList[index].size(); i++) {
//                System.out.println(arrList[index].get(i));
                if(!visit[arrList[index].get(i)]) {
                    visit[arrList[index].get(i)] = true;
                    queue.add(arrList[index].get(i));
                }
            }
        }
        return false;
    }
}