백준 9205 - Java

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

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

 

집 - 편의점들 - 페스티벌 장소 이렇게 각각의 장소를 posInfo에 저장. 

50m에 맥주 하나씩 먹으므로 맨허튼 거리로 계산했을 때 1000까지가 최대 움직일 수 있는 거리이다. 움직일 수 있는 반경에 있는 장소들을 선으로 연결해서 그래프를 만들고, 그 그래프를 탐색했을 때 페스티벌 장소에 도착할 수 있는지에 따라 결과를 출력하면 된다. 

 

 

DFS 한번 쭉 돈다음에 도착지점을 방문했는지 여부로 출력해도 되고, BFS 돌려도 된다. 

import java.io.*;
import java.util.*;
public class Main {
    public static ArrayList<Pos> posInfo;
    public static ArrayList<Integer>[] roadInfo;
    public static boolean[] isVisited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());

        for (int t = 0; t < test; t++) {
            int conv = Integer.parseInt(br.readLine());
            posInfo = new ArrayList<>();
            roadInfo = new ArrayList[conv+2]; // 각 지점마다 연결 여부 판단
            isVisited = new boolean[conv+2];

            for (int i = 0; i < conv+2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                posInfo.add(new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
                roadInfo[i] = new ArrayList<>();

            }

            for (int i = 0; i < posInfo.size(); i++) {
                for (int j = i+1; j < posInfo.size(); j++) {
                    if (dist(posInfo.get(i), posInfo.get(j))) {
                        roadInfo[i].add(j); // posInfo 리스트 몇번 장소끼리 연결되어있는지 정보를 roadInfo에 저장.
                        roadInfo[j].add(i);
                    }
                }
            }

            DFS(0);
            if (isVisited[conv+1]) {
                System.out.println("happy");
            } else {
                System.out.println("sad");
            }
        }

    }

    public static void DFS (int start) {
        isVisited[start] = true;
        for (int i : roadInfo[start]) {
            if (!isVisited[i]) {
                DFS(i);
            }
        }
    }
    public static boolean dist (Pos a, Pos b) {
        if (Math.abs(a.x - b.x) + Math.abs(a.y - b.y) <= 1000) {
            return true;
        }
        return false;
    }
    public static class Pos {
        int x;
        int y;

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