160108A(금)

ACM-ICPC - BRAVEDUCK

 

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

class Entity {
 int x, y;
 boolean visitFlag;

 public Entity(int x, int y) {
  this.x = x;
  this.y = y;
 }
 
 public boolean isVisited() {
  return visitFlag;
 }
 
 public void setVisited() {
  visitFlag = true;
 }
 
 public void unsetVisited() {
  visitFlag = false;
 }
}

public class Main {

 public static void main(String[] args) throws IOException {
  int T;
  int J;
  int N;

  int startX, startY;
  int endX, endY;
  int curX, curY;

  boolean flag;

  Entity stone[];
  
  Stack S = new Stack();
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

  for(int i = 0; i < T; i++) {
   flag = false;

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

   String split[] = br.readLine().split(" ");
   startX = Integer.parseInt(split[0]);
   startY = Integer.parseInt(split[1]);
   Entity startEntity = new Entity(startX, startY);

   split = br.readLine().split(" ");
   endX = Integer.parseInt(split[0]);
   endY = Integer.parseInt(split[1]);
   Entity endEntity = new Entity(endX, endY);

   N = Integer.parseInt(br.readLine());
   stone = new Entity[N + 2];
   
   stone[0] = startEntity;
   stone[N + 1] = endEntity;
   
   for(int j = 1; j < N + 1; j++) {
    split = br.readLine().split(" ");
    stone[j] = new Entity(Integer.parseInt(split[0]), Integer.parseInt(split[1]));
   }
   
   Entity current;
   S.push(stone[0]);
   while(!S.isEmpty()) {
    current = (Entity) S.pop();
    current.setVisited();
    
    if(current == stone[N + 1]) {
     flag = true;
     
     break;
    }
    
    for(int k = 1; k < N + 2; k++) {
     double distance = Math.sqrt(Math.pow(current.x - stone[k].x, 2) + Math.pow(current.y - stone[k].y, 2));
     
     if(distance <= J && !stone[k].isVisited()) {
      S.push(stone[k]);
     }
    }
   }

   if(flag == true) {
    System.out.println("YES");
   }
   else {
    System.out.println("NO");
   }
  }
 }
}

---

 

그래프의 DFS 개념으로 생각하여 스택을 사용해서 풀이하였다.

여전히 오답이란다.

뭐지....