알고리즘 관련/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--;
}
}
}