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

문제

www.acmicpc.net/problem/9205

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

문제해결방법

이 문제는 집, 편의점, 펜타포트 락 페스티벌 좌표를 그래프의 정점으로 가정하고 풀었다.

각 좌표에서 다른 좌표까지의 거리가 1000이하라면 두 정점을 간선으로 연결해준다.

집 정점을 시작으로 BFS를 돌면서 락 페스티벌 정점까지 도착할 수 있다면 happy, 없으면 sad를 출력했다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main9205_맥주마시면서걸어가기 {
    public static int N, mapX, mapY;
    public static int[] home, festival;
    public static List<int[]> market = new ArrayList<>();
    public static List<Integer>[] graph;
 
    public static int getDistance(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
    
    public static boolean bfs() {
        boolean arrived = false;
        boolean[] v = new boolean[N+2];
        Queue<Integer> q = new ArrayDeque<>();
        q.add(0);
        v[0] = true;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int next : graph[cur]) {
                if(v[next]==false) {
                    if(next==N+1) return true;
                    v[next] = true;
                    q.add(next);
                }
            }
        }
        return arrived;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int tc = Integer.parseInt(br.readLine());
        for(int test_case = 0; test_case<tc; test_case++) {
            market.clear();
            N = Integer.parseInt(br.readLine());
            graph = new List[N+2];
            for(int i=0; i<N+2; i++) graph[i] = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            home = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            market.add(home);
            for(int i=0; i<N; i++) {
                st = new StringTokenizer(br.readLine());
                market.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
            }
            st = new StringTokenizer(br.readLine());
            festival = new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
            market.add(festival);
            for(int i=0; i<market.size(); i++) {
                for(int j=0; j<market.size(); j++) {
                    if(i!=j && getDistance(market.get(i), market.get(j))<=1000) graph[i].add(j);
                }
            }
            String result = bfs()?"happy":"sad";
            System.out.println(result);
        }
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.