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

문제

• BOJ 9205
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

어떤 편의점을 먼저 선택할지 상관 없이 페스티벌에 도착하기만 하면 된다. 따라서 모든 좌표들을 배열에 넣고 방문할 좌표를 넣을 큐를 만든다. 그리고 큐에서 꺼낸 좌표를 현재 좌표라 생각하고, 배열에 저장된 다른 좌표들을 검색하면서 거리가 1000이상인지 아닌지를 판단한다. 만약 1000이하이면 방문할 수 있으므로 큐에 넣어주고, 1000보다 크다면 큐에 아무값도 들어가지지 않으므로 더이상 간선이 만들어지지 않기 때문에 종료된다. 이떄, isStop이라는 변수를 통해 페스티벌까지 갔는지 아닌지를 판단한다.

코드

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 {

	static int T;
	static int N; // 편의점 개수
	static Point[] nodes;
	static boolean[] visited;
	static Point festival; //페스티벌 좌표
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

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

		for (int tc = 0; tc < T; tc++) {
			N = Integer.parseInt(br.readLine());// 편의점 개수
			nodes = new Point[N+2];
			visited = new boolean[N+2];

			//집, 편의점, 페스티벌 좌표 입력받음
			for (int idx = 0; idx < N+2; idx++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				nodes[idx] = new Point(x, y);
			}

			festival = nodes[N+1]; //페스티벌 좌표
			
			//bfs
			Queue<Point> queue = new LinkedList<Point>();
			queue.offer(nodes[0]); //첫 시작정점
			visited[0] = true; //방문표시
			
			boolean isStop = true;
			
			while(!queue.isEmpty()) {
				Point point = queue.poll();
				int currentX = point.x;
				int currentY = point.y;
				
				if(point.equals(festival)) { //페스티벌에 도착했다면
					sb.append("happy\n");
					isStop = false;
					break;
				}
				
				for(int i=1; i<N+2; i++) {
					if(!visited[i] && Math.abs(currentX - nodes[i].x) + Math.abs(currentY - nodes[i].y) <= 1000){
	    				visited[i] = true;
	    				queue.offer(nodes[i]);
	    			}
				}
			}
			
			if(isStop) { //도착못했다면
				sb.append("sad\n");
			}
		}
		System.out.println(sb.toString());
	}

	static class Point {
		int x;
		int y;

		public Point() {
		}

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