문제 풀이(1)

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Node{
	int x;
	int y;

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

public class Main {

	static int T ;

	static ArrayList<Node> list; 

	static ArrayList<Integer>[] adj;

	static boolean[] visited;

	static int n;

	public static void main(String[] args)  throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		T = Integer.parseInt(br.readLine());


		while (T-- > 0) {
			
			n = Integer.parseInt(br.readLine());

			visited = new boolean[n + 2];

			list = new ArrayList<>();

			

			for (int i = 0; i < n + 2; i++) {
				
				StringTokenizer st = new StringTokenizer(br.readLine());

				int x = Integer.parseInt(st.nextToken());

				int y = Integer.parseInt(st.nextToken());

				list.add(new Node(x, y));

			}

			adj = new ArrayList[n + 2];

			for (int i = 0; i < n + 2; i++) {
				adj[i] = new ArrayList<>();
			}

			for (int i = 0; i < n + 2; i++) {
				
				for (int j = i + 1; j < n + 2; j++) {
					
					if (function(list.get(i) , list.get(j))) {
						
						adj[i].add(j);
						adj[j].add(i);
					}

				}
			}


			System.out.println( bfs() );
		}

	}


	public static String bfs()
	{
		Queue<Integer>Q = new LinkedList<>();

		Q.offer(0);

		visited[0] = true;


		while (!Q.isEmpty()) {
			
			int now = Q.poll();

			if (now == n + 1) {
				return "happy";
			}

			for(int next : adj[now])
			{
				if (visited[next])continue;

				visited[next] = true;

				Q.offer(next);
			}

		}


		return "sad";

	}


	public static boolean function(Node n1 , Node n2)
	{

		int result = Math.abs(n1.x - n2.x) + Math.abs(n1.y - n2.y);

		return result <= 1000;
	}
}

Node

Node 클래스는 (x, y) 좌표를 나타내는 클래스이다.

Main

T 변수: 테스트 케이스의 개수를 저장하는 변수이다.
list : Node 객체를 저장하는 ArrayList이다.
adj : 인접 리스트로 가중치 없는 그래프이다.
visited : 정점의 방문 여부를 저장하는 boolean 배열이다.
n : 편의점의 개수를 저장하는 변수이다.

main

테스트 케이스의 개수 T를 입력 받는다.
편의점의 개수 n을 입력 받는다.
list에 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표를 저장한다.
adj 배열을 초기화합니다.
모든 편의점 간에 이동 가능 여부를 확인하고, 이동 가능한 경우 adj에 정점과 간선을 추가한다.
BFS 알고리즘을 사용하여 상근이네 집에서 펜타포트 락 페스티벌까지 이동 가능 여부를 확인한다.

bfs

BFS 알고리즘을 사용하여 상근이네 집에서 펜타포트 락 페스티벌까지 이동 가능 여부를 확인하는 메서드이다.큐를 사용하여 너비 우선 탐색을 수행한다.현재 위치에서 이동 가능한 정점들을 큐에 추가하고, 이미 방문한 정점은 무시한다.펜타포트 락 페스티벌에 도달하면 "happy"를 반환하고, 도달하지 못하면 "sad"를 반환한다.

function

두 노드 n1과 n2 사이의 거리를 계산하여 이동 가능 여부를 반환하는 메서드이다. 거리가 1000 이하인 경우에만 이동 가능하다는 조건을 설정한다.