[BOJ 9205] 맥주 마시면서 걸어가기 (Java)

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

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

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 Main_BOJ_9205_1 {
	static class Edge{
		int id, cost;
		Edge(int id, int cost){
			this.id=id;
			this.cost=cost;
		}
	}
	static int T, N;
	static ArrayList<ArrayList<Edge>> adjList;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		T=Integer.parseInt(br.readLine());
		for (int t=1; t<=T; t++) {
			N=Integer.parseInt(br.readLine());
			ArrayList<int[]> positions=new ArrayList<>();
			adjList=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());
				positions.add(new int[] {x,y});
				adjList.add(new ArrayList<>());
			}
			for (int i=0; i<N+1; i++) {
				for (int j=i+1; j<N+2; j++) {
					int cost=Math.abs(positions.get(i)[0]-positions.get(j)[0])+Math.abs(positions.get(i)[1]-positions.get(j)[1]);
					if (cost>1000) continue;
					adjList.get(i).add(new Edge(j, cost));
					adjList.get(j).add(new Edge(i, cost));
				}
			}
			if (bfs(0)) System.out.println("happy");
			else System.out.println("sad");
		}
	}

	private static boolean bfs(int num) {
		boolean[] visited=new boolean[N+2];
		Queue<Edge> q=new LinkedList<>();
		q.add(new Edge(0, 0));
		visited[0]=true;
		while (!q.isEmpty()) {
			Edge curr=q.poll();
			if (curr.id==N+1) return true;
			for (int i=0; i<adjList.get(curr.id).size(); i++) {
				int id=adjList.get(curr.id).get(i).id;
				int cost=adjList.get(curr.id).get(i).cost;
				if (!visited[id]) {
					visited[id]=true;
					q.add(new Edge(id, curr.cost+cost));
				}
			}	
		}
		return false;
	}
}

bfs로 풀 수 있다.

인접 정점을 계산하는 방식은 이렇다: 나를 제외한 모든 정점의 맨해튼 거리를 계산해서, 맨해튼 거리가 1000 이하인 정점에 대해 인접 정점으로 삼아준다.

(최대로 갈 수 있는 거리가 20병*50m 이므로)

 

출발점 0부터 시작해서, 탐색을 해준 후 도착 지점을 만난다면 갈 수 있는 경우이다.