알고리즘 관련/BOJ

9205 맥주 마시면서 걸어가기

Andrew-Yun 2021. 12. 27. 15:20

문제: https://www.acmicpc.net/problem/9205

 

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

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.

www.acmicpc.net

시작 지점부터 근처의 편의점을 들를 수 있다면, 탐색하여 진행하는 과정이 BFS와 유사했고, N의 크기가 100이하로 작기 때문에, BFS로도 충분히 해결할 수 있다고 판단했다.

 

음수 좌표 값을 간편하게 처리하기 위해서 시작 지점과, 편의점, 도착 지점들을 클래스의 인스턴스로 생성하여 hashmap의 형태로 키에 넣었다.

이후 맨해튼 거리가 1000이하라면 큐에 넣어 탐색하도록 구현했다.

import java.io.*;
import java.util.*;
class Node{
  int x, y;
  public Node(int x, int y){
    this.x = x;
    this.y = y;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) {
      return true;
    }
    if (o == null || getClass() != o.getClass()) {
      return false;
    }
    Node node = (Node) o;
    return x == node.x && y == node.y;
  }

  @Override
  public int hashCode() {
    return Objects.hash(x, y);
  }

  @Override
  public String toString() {
    return "Node{" +
        "x=" + x +
        ", y=" + y +
        '}';
  }
}
public class Main {
  public static int MAX_DIST = 1000;
  public static int STORE;
  public static Node Start, End;
  public static HashMap<Node, Boolean> visit;
  public static void bfs(){
    Queue<Node> q = new ArrayDeque<>();
    q.add(Start);
    visit.put(Start, true);
    while(!q.isEmpty()){
      Node cur = q.poll();
      for(Node next : visit.keySet()){
        if(next == cur)
          continue;
        int x_dist = Math.abs(cur.x - next.x);
        int y_dist = Math.abs(cur.y - next.y);
        if(visit.get(next) == false &&
            x_dist + y_dist <= MAX_DIST){
          visit.put(next, true);
          q.add(next);
        }
      }
    }
  }
  public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int T = Integer.parseInt(st.nextToken());
    while(T != 0){
      visit = new HashMap<>();
      st = new StringTokenizer(br.readLine());
      STORE = Integer.parseInt(st.nextToken());

      st = new StringTokenizer(br.readLine());
      Start = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
      visit.put(Start, false);

      for(int i = 0; i < STORE; i++){
        st = new StringTokenizer(br.readLine());
        Node n = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        visit.put(n, false);
      }

      st = new StringTokenizer(br.readLine());
      End = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
      visit.put(End, false);
      //bfs
      bfs();
      if (visit.get(End) == false)
        System.out.println("sad");
      else
        System.out.println("happy");
      T--;
    }
  }
}