9205_맥주 마시면서 걸어가기

사용 알고리즘: bfs

사용 언어: java

 

 

일단 한 번 틀림

이때 로직은, pq를 만들어서, 시작점에서 가장 가까운 편의점부터 줄 세움.

package week21;

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

public class Main_bj_9205_맥주마시면서걸어가기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int t=0; t<testcase; t++) {
			int n = sc.nextInt(); //편의점의 개수
			int[][] endPoint = new int[2][2]; //집,락페
			Queue<int[]> pq = new PriorityQueue<>((o1, o2) 
					-> (Math.abs(endPoint[0][0]-o1[0])+Math.abs(endPoint[1][0]-o1[1])) - (Math.abs(endPoint[0][1]-o2[0])+Math.abs(endPoint[1][1]-o2[1]))); //집에서 가까운 순으로 정렬
			endPoint[0][0] = sc.nextInt();
			endPoint[0][1] = sc.nextInt(); //집 좌표
			
			for(int i=0; i<n; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				
				pq.add(new int[] {x, y});
			}
			
			endPoint[1][0] = sc.nextInt();
			endPoint[1][1] = sc.nextInt(); //락페 좌표
			
			if(canGo(n, endPoint, pq)) System.out.println("happy");
			else System.out.println("sad");
			
//			while(!pq.isEmpty()) {
//				System.out.println(Arrays.toString(pq.poll()));
//			}
			
		}//
	}
	
	private static boolean canGo(int n, int[][] endPoint, Queue<int[]> pq) {
		int cur[] = new int[] {endPoint[0][0], endPoint[0][1]};
		
		while(!pq.isEmpty()) {
			int[] nxtConv = pq.poll();
			int goStraight = canTmpGo(cur, endPoint[1]);
			int goNxtConv = canTmpGo(cur, nxtConv);
			
			if(goStraight >= 0) //편의점을 거치치 않고도 바로 갈 수 있음
				return true; 
			
			if(goNxtConv < 0) //다음 편의점조차 갈 수 없으면 못 감
				return false;
			
			//다음 편의점으로만 갈 수 있는 경우, 맥주를 20개 채워 온다.
			cur = nxtConv;
		}
		//마지막 장소에서 확인(모든 편의점을 거쳐야 할 때는, 이미 pq가 비어있는 상태이기 때문에 한 번 더 확인 필요)
		int goStraight = canTmpGo(cur, endPoint[1]);
		
		if(goStraight >= 0) //편의점을 거치치 않고도 바로 갈 수 있음
			return true; 
		
		return false;
	}
	
	private static int canTmpGo(int[] start, int[] end) {
		return Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]) <= 1000 ? 1 : -1;
		
		//맥주가 최대로 찼을 떄, 최대 50*20 = 1000m 움직일 수 있음.
		//따라서 '거리'가 1000 이하이면 갈 수 있음
		
	}

}

 

 

위의 코드의 문제점? -> 시작점에서 가까운 편의점으로 옮겼을 때, 그 다음 가까운 애가 꼭 현재 편의점과 제일 가까운 애라고 할 수 없음.

고친 코드는, 시작점에서 20병의 맥주 이내로 갈 수 있는 모든 좌표를 queue에 넣고, 그 편의점을 기준으로 해서 또 다시 다음 움직일 곳을 찾아간다.

package week21;

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

public class Main_bj_9205_맥주마시면서걸어가기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int t=0; t<testcase; t++) {
			int n = sc.nextInt(); //편의점의 개수
			int[][] endPoint = new int[2][2]; //집,락페
			List<int[]> convens = new ArrayList<>();
			endPoint[0][0] = sc.nextInt();
			endPoint[0][1] = sc.nextInt(); //집 좌표
			
			for(int i=0; i<n; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				
				convens.add(new int[] {x, y});
			}
			
			endPoint[1][0] = sc.nextInt();
			endPoint[1][1] = sc.nextInt(); //락페 좌표
			
			if(canGo(n, endPoint, convens) >= 0) System.out.println("happy");
			else System.out.println("sad");
			
//			while(!pq.isEmpty()) {
//				System.out.println(Arrays.toString(pq.poll()));
//			}
			
		}//
	}
	
	private static int canGo(int n, int[][] endPoint, List<int[]> convens) {
		Queue<Beer> q = new ArrayDeque<>();
		q.add(new Beer(endPoint[0], 0)); //좌표, 움직인 횟수
		while(!q.isEmpty()) {
			Beer cur = q.poll();
			
			if(canTmpGo(cur.point, endPoint[1]) > 0) {
				//다음 편의점 거치지 않고 갈 수 있으면
				return cur.move;
			}
			
			//남은 편의점 중에서, 50*20 이내 거리에 있는 편의점 집어 넣기
			for(int i=convens.size() - 1; i>=0; i--) {
				if(canTmpGo(cur.point, convens.get(i)) > 0) {
					q.add(new Beer(convens.get(i), cur.move + 1));
					convens.remove(i);
				}
			}
		}
		return -1; //못 가면 음수 출력
	}
	
	private static int canTmpGo(int[] start, int[] end) {
		return Math.abs(start[0] - end[0]) + Math.abs(start[1] - end[1]) <= 1000 ? 1 : -1;
		
		//맥주가 최대로 찼을 떄, 최대 50*20 = 1000m 움직일 수 있음.
		//따라서 '거리'가 1000 이하이면 갈 수 있음
		
	}

}
class Beer {
	int[] point;
	int move;
	public Beer(int[] point, int move) {
		this.point = point;
		this.move = move;
	}
}