[백준 / BOJ] 9205번 : 맥주 마시면서 걸어가기 - JAVA

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

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

BFS

어떤 편의점을 방문해야할지 모르기 때문에 BFS를 사용했다. 가장 먼저 떠올린 것은 가까이 있는 순서대로 방문하는 것이었으나, 가장 가까이 있는 편의점이 오히려 공연장과 멀어지거나, 혹은 다른 편의점들과 거리가 멀어 다음 편의점에 도달하지 못하는 경우가 있을 수 있다. 따라서 현재 위치에서 방문할 수 있는 경우를 Queue에 담아두고, 그곳에서 다시 방문할 수 있는 곳을 찾는 게 합리적이다.

 

한 번에 움직일 수 있는 거리는 1000이기 때문에 (맥주 20병 * 50) 현재 위치와 다음 편의점 사이 거리가 1000 이하인 경우 Queue에 담도록 했다. 방문 체크도 해주었는데, 이는 편의점에 들를 때마다 맥주를 20병 꽉 채울 수 있기 때문에, 만일 어떤 편의점에 지금 도달할 수 있다면, 다른 곳을 거쳐서 다시 방문할 필요가 없기 때문이다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 시간 : 100ms
// 메모리 : 12488KB
public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		while(T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
            boolean[] v = new boolean[N];
			Queue<int[]> que = new LinkedList<>();
			que.offer(new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
			int[][] map = new int[N][2];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				map[i][0] = Integer.parseInt(st.nextToken());
				map[i][1] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			int er = Integer.parseInt(st.nextToken());
			int ec = Integer.parseInt(st.nextToken());
			
			boolean flag = false;
			while(!que.isEmpty()) {
				int[] cur = que.poll();
				if(Math.abs(cur[0] - er) + Math.abs(cur[1] - ec) <= 1000) {
					flag = true;
					break;
				}
				for (int i = 0; i < N; i++) {
					if(v[i]) continue;
					int dist = Math.abs(cur[0] - map[i][0]) + Math.abs(cur[1] - map[i][1]);
					if(dist <= 1000) {
						que.offer(new int[] {map[i][0], map[i][1]});
						v[i] = true;
					}
				}
			}
			if(!flag) sb.append("sad\n");
			else sb.append("happy\n");
		}
		System.out.println(sb);
	}


}