맥주 마시면서 걸어가기
백준 9205: 맥주 마시면서 걸어가기
풀이
편의점의 위치가 상근이네 집에서 가까운 순서대로 주어지는 것이 아님
-> 편의점의 위치를 모두 확인해 봐야함!
소스코드
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");
}
}
}