알고리즘 스터디 - 7주차 2

9205

• 알고리즘 : 너비 우선 탐색
• 난이도 : 골드5

문제

9205

접근

• 패스티발에 접근하기 위해 각 지점을 노드로 생각했다.
• 노드가 아닌 격자 그래프로 생각하면 너무 크기가 커진다.
• 노드를 저장하고 노드를 통해서 BFS로 푼다.

풀어보기

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int store;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(reader.readLine());
		for(int i = 0; i < t; i++) {
			store = Integer.parseInt(reader.readLine());
			Nodes[] nodes = new Nodes[store + 2];
			String[] tempHome = reader.readLine().split(" ");
			int homeX = Integer.parseInt(tempHome[0]);
			int homeY = Integer.parseInt(tempHome[1]);
			nodes[0] = new Nodes(homeX, homeY);
			for(int j = 1; j < store + 1; j++) {
				String[] temp = reader.readLine().split(" ");
				int x = Integer.parseInt(temp[0]);
				int y = Integer.parseInt(temp[1]);
				nodes[j] = new Nodes(x, y);
			}
			String[] tempFestival = reader.readLine().split(" ");
			int festivalX = Integer.parseInt(tempFestival[0]);
			int festivalY = Integer.parseInt(tempFestival[1]);
			nodes[store+1] = new Nodes(festivalX, festivalY);
			System.out.println(bfs(nodes) ? "happy" : "sad");
		}
	}

	static boolean bfs(Nodes[] nodes){
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[nodes.length];
		queue.add(0);
		visited[0] = true;
		while(!queue.isEmpty()){
			int current = queue.poll();
			if(current == nodes.length - 1){
				return true;
			}
			for(int i = 0; i< nodes.length; i++){
				if(!visited[i]){
					int dist = getDistance(nodes[current], nodes[i]);
					if(dist <= 1000){
						visited[i] = true;
						queue.add(i);
					}
				}
			}

		}

		return false;
	}

	private static int getDistance(Nodes node, Nodes node1) {
		return Math.abs(node.x - node1.x) + Math.abs(node.y - node1.y);
	}

	static class Nodes{
		int x;
		int y;

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

시행착오

• 거리를 계산하는 함수가 필요 했다.
• 거리가 1000보다 낮을 때 다음 노드를 접근할 수 있도록 한다