[백준] 알고리즘 분류(그래프 이론,JAVA)9205번, 맥주 마시면서 걸어가기

문제 링크

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

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 맥주 한 박스에는 맥주가 20개가 들어있습니다.

2. 상근이는 50미터를 이동할 때마다 맥주 1개를 마십니다.

3. 상근이는 편의점에 도착했을 때 맥주 한 박스를 리필할 수 있습니다.

4. 집, 편의점, 페스티벌 목적지가 존재할 때 집에서 목적지에 갈 수 있으면 "happy" 불가능하면 "sad" 결과로 출력합니다.

5. 두 좌표 사이의 거리는 |x좌표의 차이  + y좌표의 차이| 입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. BFS를 사용하여 목적지에 도착할 수 있는지 확인합니다.

 

3. 탐색이 끝났을 때 목적지에 도착하면 "happy" 불가능하면 "sad"를 결과로 출력합니다.

 

BFS 탐색!

 

BFS를 탐색할 때 모든 편의점을 탐색하며, 거리가 1000미터 이내에 있는 편의점을 탐색합니다.

 

방문 배열 Boolean 형 visited[]을 사용하여 편의점을 방문하였는지 확인하여 중복탐색을 방지하였습니다.

 

1. 집을 시작점으로 1000미터 이내에 편의점을 찾아서 출발합니다.

 

2. 위 과정을 반복하여 페스티벌에 도착하는지 확인합니다.

 

이 과정을 진행되는 것을 예제입력을 통해서 보여드리겠습니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

※1번째 테스트케이스의 경우만 보여드리겠습니다.

 

N : 2

집 : (0, 0)

편의점 : (1000, 0), (1000, 1000)

페스티벌 장소 : (2000, 1000)

 

2. BFS를 사용하여 목적지에 도착할 수 있는지 확인합니다.

 

1. 집을 시작점으로 1000미터 이내에 편의점을 찾아서 출발합니다.

집에서 1000미터 이내 편의점 1로 이동!

현재 위치 : 편의점 1

 

편의점1 에서 1000미터 이내 편의점 2로 이동!

현재 위치 : 편의점 2

 

2. 위 과정을 반복하여 페스티벌에 도착하는지 확인합니다.

 

 

편의점 2에서 1000미터 이내에 축제 장소 존재!

 

축제 장소 도착 성공~

 

3. 탐색이 끝났을 때 목적지에 도착하면 "happy" 불가능하면 "sad"를 결과로 출력합니다.

 

도착 성공!

"happy" 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 집, 편의점, 축제 좌표를 띄어쓰기 기준 나누었습니다.
• 각 테스트케이스마다 bfs함수를 실행하여 집에서 축제 위치를 도착하는지 확인합니다.
• 축제에 도착하면 StringBuilder에 "happy", 불가능하면 "sad"를 저장합니다.
• System.out.print()을 이용하여 StringBuilder에 저장된 결과를 출력하였습니다.

• bfs함수는 집에서 1000미터 이내의 편의점들로 이동하며 축제에 도착 가능한지 탐색합니다.
• check함수는 두 좌표 사이의 거리가 1000미터 이내인지 확인합니다.

 

결과코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //좌표 관련 클래스
    static class Pos{
        int r, c;	//r : row, c : column
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    //편의점 위치 정보 배열
    static Pos[] arr;
    static int N, sr, sc, er, ec;	//sr , sc : 집의 위치 er, dc : 축제 위치
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        //각 테스트케이스 진행
        for(int tc = 1;tc<=T;tc++){
            //입력값 저장
            N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine()," ");
            //집의 위치 저저장
            sr = Integer.parseInt(st.nextToken());
            sc = Integer.parseInt(st.nextToken());
            arr = new Pos[N];
            //편의점 위치 저장
            for(int i=0;i<N;i++) {
                st = new StringTokenizer(br.readLine()," ");
                arr[i] = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }
            st = new StringTokenizer(br.readLine()," ");
            //축제 위치 저장
            er = Integer.parseInt(st.nextToken());
            ec = Integer.parseInt(st.nextToken());
            //bfs탐색으로 축제 위치에 도착 가능한지 확인
            if(bfs())
                sb.append("happy\n");	//도착 성공!
            else
                sb.append("sad\n");		//도착 실패!
        }
        System.out.print(sb);	//결과 출력
    }
    static boolean bfs(){
        //BFS에 사용할 Queue
        Queue<Pos> q = new ArrayDeque<>();
        //편의점 방문 확인 배열
        boolean[] visited = new boolean[N];
        q.offer(new Pos(sr, sc));	//집의 위치 Queue 저장
        //BFS  탐색 진행!
        while(!q.isEmpty()){
            Pos cur = q.poll();
            //축제 장소 도착 성공 시
            if(check(cur.r , cur.c, er, ec))
                return true;
            //1000미터 이내 인접한 편의점 탐색
            for(int i=0;i<N;i++) {
                if (visited[i])	//이미 방문한 편의점은 Pass
                    continue;
                Pos nxt = arr[i];
                //방문 가능한 편의점일 때
                if (check(cur.r, cur.c, nxt.r, nxt.c)) {
                    visited[i] = true;	//방문 확인
                    q.offer(new Pos(nxt.r, nxt.c));	//다음 편의점 Queue 저장
                }
            }
        }
        return false;	//모든 탐색이 끝난 뒤에 축제 장소 도착 실패!
    }
    //좌표 사이의 거리가 1000미터 이내인지 확인하는 함수
    static boolean check(int sr, int sc, int er, int ec){
        int dis = Math.abs(sr - er) + Math.abs(sc - ec);	//거리 구하기
        if(dis <= 1000)	//1000미터 이내일 때
            return true;
        return false;	//1000미터 이내가 아닐 때
    }
}