맥주 마시면서 걸어가기(백준 9205번), 자바(☆☆)

9205번: 맥주 마시면서 걸어가기 (acmicpc.net)

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

 

1. 모든 편의점을 들러야하는 것은 아니다. 목적지로만 갈 수 있으면 됨

2. 집에서 출발할 때부터,  거리가 1000이하인 장소만 이동할 수 있음  

 

 

1. 오답

->편의점을 거치지 않아도 된다는 점을 고려하지 못하였다.

import java.util.*;

public class Main {
	

	public static void main(String[] args) {
		
		int t; 
		int n;//편의점 개수 
		ArrayList<Point> store=new ArrayList<>();
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		
		boolean check;
		
		while(t-->0) {
			store.clear();
			check=true;
			n=sc.nextInt();
			while(n-->=-1) {
				store.add(new Point(sc.nextInt(),sc.nextInt()));
			}
			
			int distance=0;
			int cnt=20;
			for(int i=0;i<store.size()-1;i++) {
				distance+=(store.get(i+1).x-store.get(i).x)
						+(store.get(i+1).y-store.get(i).y);
				
				if((distance/50)>cnt) {
					check=false;
					break;
				}
				else {
					cnt-=(distance/50);
					distance%=50;
				}	
				cnt+=20;
				}
		
			if(!check) 
				System.out.println("sad");
			else System.out.println("happy");
			}
			
	}
		
	
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
}

 

 

2. Queue 이용 (7%에서 실패)

추가 반영한 반례

1
1
2000 0
1000 0
3000 0
정답: happy

1
2
0 0 
-1000 0 
1000 0
2000 0 
정답: happy

import java.util.*;

public class Main2 {
	

	public static void main(String[] args) {
		
		int t; 
		int n;//편의점 개수 
		Queue <Point> q=new LinkedList<>();
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		
		boolean check;
		
		while(t-->0) {
			check=false;
			n=sc.nextInt();
			Point temp=new Point(sc.nextInt(),sc.nextInt());//집
			while(n-->0) {
				q.add(new Point(sc.nextInt(),sc.nextInt()));
			}
			Point dest=new Point(sc.nextInt(),sc.nextInt());//목적지
			int max=check(temp.x, temp.y,dest.x,dest.y); //집에서 목적지까지의 거리 
			if(max<=1000) {
				System.out.println("happy"); continue;
			}
			
			while(!q.isEmpty()) {
				Point p=q.poll();
				if(check(p.x,p.y,temp.x,temp.y)>1000) continue; //현재 위치와 편의점 사이의 거리가 1000이 넘는 경우 
				else {
					if(max>check(dest.x,dest.y,p.x,p.y)) temp=p;
				}
				if(check(dest.x,dest.y,p.x,p.y)<=1000) { //현재 위치에서 목적지까지의 거리가 1000이내인 경우 
					check=true; break;
				}
				
			}
			if(check) System.out.println("happy");
			else System.out.println("sad");
		}
		
	}
		
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	
	static public int check(int x, int y, int dx, int dy) {
		
		return Math.abs(x-dx)+Math.abs(y-dy);
	
	}
}

 

3. ArrayList와 Queue, BFS 이용(성공)

추가반영해야할 반례

1
4
2000 0
1000 0
0 0
0 1000
0 2000
1000 2000
정답: happy

 

3.  큐 사용 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		int t; 
		int n;//편의점 개수 
		Queue <Point> q=new LinkedList<>();
		Scanner sc=new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t=Integer.parseInt(br.readLine());
		
		boolean check;
		
		while(t-->0) {
			
			check=false;
			n=Integer.parseInt(br.readLine());
			ArrayList<Point> arr=new ArrayList<Point>();
			q.clear();
			
			//집의 좌표를 넣고, 이동하는 좌표를 add
			q.add(new Point(sc.nextInt(),sc.nextInt()));
			
			//편의점, 페스티벌의 좌표 
			while(n-->-1) { 
				arr.add(new Point(sc.nextInt(),sc.nextInt()));
			}
			
			//페스티벌의 좌표 
			Point dest=new Point(arr.get(arr.size()-1).x, arr.get(arr.size()-1).y); //목적지 주소 
		
			
			while(!q.isEmpty()) {
				Point p=q.poll();
				
				//목적지에 도착했다면
				if(p.x==dest.x && p.y==dest.y) {
					check=true;
					break;
				}
				
				for(int i=0;i<arr.size();i++) {
					
					//현재 위치에서 1000이하인 좌표 q에 넣기 
					if(getDistance(p.x, p.y, arr.get(i).x, arr.get(i).y)<=1000) {
						q.add(new Point(arr.get(i).x, arr.get(i).y));
						arr.remove(i); //편의점 목록에서 해당 좌표 제거 
						i--; 
					}
				}
				
			}
			if(check) System.out.println("happy");
			else System.out.println("sad");
				
			}
	}
	
		
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	
	//거리구하기 
	static public int getDistance(int x, int y, int dx, int dy) { 
		
		return Math.abs(x-dx)+Math.abs(y-dy);
	
	}
}

 

 

4. 플로이드 워셜(성공)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main{
	
	static boolean[][] reachable;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		int T; 
		int N;//편의점 개수
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T=Integer.parseInt(br.readLine());
		
		for(int t_c=1;t_c<=T;t_c++) {
			
			N=Integer.parseInt(br.readLine());
			
			ArrayList<Point> arr=new ArrayList<Point>(); //모든 좌표 저장 
			
			reachable=new boolean[N+2][N+2];
			
			
			for(int i=0;i<N+2;i++) {
				StringTokenizer st=new StringTokenizer(br.readLine());
				arr.add(new Point(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
			}
			
			
			//각 지점쌍별로 이동가능 여부를 저장
			
			//1) 
			for(int i=0;i<N+2;i++) {
				for(int j=0;j<N+2;j++) {
					if(getDistance(arr.get(i).x,arr.get(i).y, arr.get(j).x, arr.get(j).y)<=1000){
						reachable[i][j]=true;
					}
				}
			}
			
			//2) 
			 for(int k=0;k<N+2;k++) {
				 for(int i=0;i<N+2;i++) {
					 for(int j=0;j<N+2;j++) {
						 if(reachable[i][k] && reachable[k][j]) { 
							 reachable[i][j]=true;
						 }
					 }
				 }
			 }
			 //마지막 목적지의 좌표 
			 int destIndex=arr.size()-1;
			 
			 //출발지 좌표: 0 에서 목적지 좌표까지 이동 가능하다면
			 if(reachable[0][destIndex]) System.out.println("happy");
			 else System.out.println("sad");
		}
	}
	
		
	static class Point{
		int x;
		int y;
		public Point(int x, int y) {
			this.x=x;
			this.y=y;
		}
	}
	
	//거리구하기 
	static public int getDistance(int x, int y, int dx, int dy) {
		
		return Math.abs(x-dx)+Math.abs(y-dy);
	
	}
	
}