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

www.acmicpc.net/problem/9205

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

2020-12-27

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main9205 {
    public static int N, dist[][]; // 0: 집 , 1 - N : 편의점, N+1 : 맥주
    public static List<Beer> list;
    
    public static class Beer {
        int x;
        int y;
 
        public Beer(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void floydWarshall() {
        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(dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int test = Integer.parseInt(st.nextToken().trim());
        
        for(int ts = 1; ts <= test; ts++) {
            st = new StringTokenizer(bf.readLine().trim());
            N = Integer.parseInt(st.nextToken());
            list = new ArrayList<>();
            dist = new int[N+2][N+2];
            
            for(int i = 0; i < N+2; i++) {
                st = new StringTokenizer(bf.readLine());                
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                list.add(new Beer(x, y));
            }
            
            for(int i = 0; i < N+2; i++) { 
                for(int j = 0; j < N+2; j++) { 
                    if(i != j) dist[i][j] = 987654321; //init
                }
            }
            
            for(int i = 0; i < N+2; i++) {
                for(int j = 0; j < N+2; j++) { // 정점사이의 거리 구하기
                    if(i != j) {
                        int res = Math.abs(list.get(i).x - list.get(j).x) 
                                + Math.abs(list.get(i).y - list.get(j).y);
                        if(res <= 1000) dist[i][j] = res;
                    }
                }
            }
            
            floydWarshall();
            if(dist[0][N+1] > 0 && dist[0][N+1] != 987654321) System.out.println("happy");
            else System.out.println("sad");
        }
    }
}
 

 

#문제풀이

1. 입력값을 받는데, 0번째는 집, 1~N번째는 편의점, N+1번째는 락 페스티벌 장소 라고 생각을 한다.

 

2. 플로이드 와샬로 풀 것 이기 때문에, dist 배열을 만들고 max 값을 넣어 초기화를 해둔다.

 

3. 맨해튼 거리 공식을 이용하여 두 정점 사이의 거리를 구하여 dist 배열에 넣는다. 이 때 1,000(50m * 20병)이하 가 아닌 경우는 값을 업데이트 하지 않았다. 

 

4. 플로이드와샬 알고리즘을 이용하여 dist 배열을 업데이트 시켜준다.

 

5. dist[0][N+1] (집-락페스티벌) 이 0 이상이며 max 값이 아닌 경우 페스티벌에 도착할 수 있다고 판단하여 "happy"를 출력해주고, 그렇지 않은 경우 "sad"를 출력해주었다.

 

 

+) Math.abs 괄호를 잘못쳐서 몇 번 틀렸었다..;