맥주 마시면서 걸어가기


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

문제보기
Alt text

풀이

편의점의 위치가 상근이네 집에서 가까운 순서대로 주어지는 것이 아님
-> 편의점의 위치를 모두 확인해 봐야함!

소스코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Node {
		int r, c;

		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int N = sc.nextInt(); // 편의점개수
			Node[] map = new Node[N + 2]; // 편의점 좌표를 담을 배열
			for (int i = 0; i < N + 2; i++) { // 좌표 map배열에 담기
				int r = sc.nextInt();
				int c = sc.nextInt();
				map[i] = new Node(r, c);
			}
			boolean visited[] = new boolean[N+2]; // 편의점 방문 여부

			Node start = map[0]; // 상근이 집 좌표(시작 위치)
			Node end = map[N + 1]; // 페스티벌 좌표(도착 위치)

			boolean flag = false;
			Queue<Node> queue = new LinkedList<>();
			queue.add(start);

			while (!queue.isEmpty()) {
				Node node = queue.poll(); // 현재 위치

				// 현재위치가 페스티벌 위치라면 성공!
				if (node.equals(end)) {
					flag = true;
					break;
				}

				for (int i = 1; i < N + 2; i++) {
					// 방문하지 않은 지점이고, 거리가 1000이하이면
					if (!visited[i] && Math.abs((map[i].r - node.r)) + Math.abs((map[i].c - node.c)) <= 1000) {
						visited[i] = true;
						queue.add(map[i]);
					}
				}
			}

			if(flag)
				System.out.println("happy");
			else
				System.out.println("sad");

		}
	}
}