[백준/JAVA] 9205_맥주 마시면서 걸어가기

백준🔗

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

 

 

문제

 

 

간단 풀이

흐어 요새 싸피가 2학기 개강을 앞두면서 프로젝트 마무리, 2학기 준비 등등 이래저래 정신없이 바빠져가지구 며칠 포스팅을 못했다ㅠㅠ 오늘도 부랴부랴 간단한 트리 BFS 문제로 가져와봤다..!!

 

맥주 한 병에 50m씩 갈 수 있고, 한 박스에는 맥주가 20개 있기 때문에 다음 경유지까지의 거리가 1000m 이내이면 이동이 가능하다.

따라서 집에서부터 페스티벌까지 가는 길에 거리가 1000m 이하인 편의점들을 선택했을 때 페스티벌에 도착할 수 있는지 확인하면 된다.

사실 최단 거리를 구하고자 하는 것이 아니기 때문에 DFS로도 큰 차이는 없을 거라는 생각이 든다.

 

문제 풀이 후에 다른 분들의 코드도 열어봤는데, 거리가 1000m 이하인 편의점들을 이어서 트리를 만든 후에 BFS를 실행한 코드들이 많았다. 그러나 BFS를 수행하면서 거리를 따져볼 수 있기 때문에 사전에 트리를 만들 필요는 없을 듯 하다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int n = Integer.parseInt(br.readLine()); // 편의점 개수
			Pos[] arr = new Pos[n + 2];
			boolean[] visited = new boolean[n + 2];
			for (int i = 0; i < n + 2; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				arr[i] = new Pos(x, y);
			}
			Queue<Pos> q = new LinkedList<>();
			q.add(arr[0]);
			visited[0] = true;
			boolean flag = false;
			here: while (!q.isEmpty()) {
				Pos cur = q.poll();
				for (int i = 0; i < n + 2; i++) {
					if (!visited[i] && getDistance(cur, arr[i]) <= 1000) {
						if (i == n + 1) {
							flag = true;
							break here;
						}
						visited[i] = true;
						q.add(arr[i]);
					}
				}
			}
			if (flag) {
				sb.append("happy");
			} else {
				sb.append("sad");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}

	static class Pos {
		int x, y;

		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static int getDistance(Pos p1, Pos p2) {
		return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
	}
}

 

참고 자료