[백준] 9205번 맥주 마시면서 걸어가기 JAVA (자바) 풀이

문제 9205(BFS)

 

 :  출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발

    맥주 한 박스에는 맥주가 20개

    맥주 1병에 50미터 전진 가능

    편의점에 들렸을 때, 빈 병은 버리고 새 맥주를 살 때 박스에 들어가는 총 맥주가 20병을 넘을 수 없다

    (편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다)

    편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다

 

 

[입력]

 :  첫째 줄에 테스트 케이스의 개수 t (t ≤ 50)

    테스트 케이스의 첫째 줄에는 편의점의 개수 n (0 ≤ n ≤ 100)

    다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 미터 좌표 ( -32768 ≤ x, y ≤ 32767)

    두 좌표 사이의 거리 = x 좌표의 차이 + y 좌표의 차이 

  

 

 [출력]

 :  각 테스트 케이스에 대해 행복하게 페스티벌에 갈 수 있으면 "happy"

    (맥주가 바닥나서 이동할 수 없으면 "sad" 출력)

 

 

 

 [문제접근]

 

1. 맨해튼 거리 공식 잘 파악할 것!

• x끼리의 차이와 y끼리의 차이의 합이 거리이므로 애초에 x, y 따로따로 저장하지 않고 합해서 저장하려고 했지만 중요한 건 맨해튼 공식은 절대값을 이용하므로 따로따로 입력받고 각자 계산해주는게 맞다
• Math.abs ( x값1 - x값 ) + Math.abs ( y값1 - y값2 )

 

2. 출력 배열 사용하지 말고 큐에다 넣어버리기

• count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천

 

3. 인덱스를 인자로 받을 것

• dist배열에 시작점부터 편의점 도착점까지 순서대로 입력을 받았기 때문에 해당 배열 값을 찾기보다는 인덱스를 인자로 받아 n+1이 입력으로 들어온다면 종료한다

 

4. 편의점을 갈 지 도착지점을 갈 지 고민하지 말 것

• 현재 내가 어느 위치까지 갈 수 있는지는 맨해튼 공식을 통해 계산한다
• 계산한 거리가 1000과 같거나 아래면 내 맥주가 모두 떨어지기 전에 어디든 한군데는 들릴 수 있다
• 그 한군데가 어딘지는 내가 계산할 필요가 없으며 방문하지 않은 곳이라면 일단 들린다
• 만약 들리는 곳이 n+1인덱스라면 도착지점이므로 종료하면 된다

 

5. bfs를 for문이나 재귀에 사용하지 말 것

• for(){ bfs } 하지말 것 (bfs 메서드 내에서 큐에 계속 추가하면서 반복하면 된다)
• bfs메서드 내에서 다시 bfs를 호출하지 말 것 (백트래킹이나 dfs와는 다르다)

       

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int t,n,dist[][];
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        
        while(t-->0){
            n = Integer.parseInt(br.readLine());
            dist = new int[n+2][2];
            visit = new boolean[n+2];
            
            for(int i=0;i<n+2;i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                dist[i][0] = Integer.parseInt(st.nextToken());
                dist[i][1] = Integer.parseInt(st.nextToken());
            }
            
            bfs(0);
        }
    }
    static void bfs(int index){
        Queue<Integer> q = new LinkedList<>();
        q.add(index);
        visit[index] = true;
        
        while(!q.isEmpty()){
            int p = q.poll();
            
            if(p==n+1){
                System.out.println("happy");
                return;
            }
            for(int i=1;i<n+2;i++){
                if(!visit[i]){
                    int distance = Math.abs(dist[p][0]-dist[i][0])
                        + Math.abs(dist[p][1]-dist[i][1]);
                    if(distance<=1000){
                        visit[i]=true;
                        q.add(i);
                    }
                }   
            }
        }
        System.out.println("sad");
    }
}

 

 [해설]
     

 :  static int t,n,dist[][];
    static boolean visit[];
 

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    t = Integer.parseInt(br.readLine()); 테스트케이스 입력
        
 :  while(t-->0){
            n = Integer.parseInt(br.readLine());  n 입력
            dist = new int[n+2][2];  x와 y좌표 저장할 배열
            visit = new boolean[n+2];  방문기록
            
            for(int i=0;i<n+2;i++){  0번째 시작지점 / n+1번째 도착지점
                StringTokenizer st = new StringTokenizer(br.readLine());
                dist[i][0] = Integer.parseInt(st.nextToken());  x좌표 입력
                dist[i][1] = Integer.parseInt(st.nextToken());  y좌표 입력
            }
            
            bfs(0);  시작지점에서부터 bfs 실행
        }
    }

 

 :  static void bfs(int index){  출발하는 dist 인덱스
        Queue<Integer> q = new LinkedList<>();  큐선언
        q.add(index);  큐에 추가
        visit[index] = true;  방문처리
        
        while(!q.isEmpty()){ 
            int p = q.poll();  큐에서 뽑기
            
            if(p==n+1){  현위치가 n+1이면 도착지점이다
                System.out.println("happy");  무사히 도착했으므로 happy
                return;
            }

            for(int i=1;i<n+2;i++){  맨해튼 공식으로 distance저장
                if(!visit[i]){  방문 전이라면 어디든 들려라
                    int distance = Math.abs(dist[p][0]-dist[i][0]) + Math.abs(dist[p][1]-dist[i][1]);
                    if(distance<=1000){  내가 갈 수 있는 위치라면 distance위치로 이동
                        visit[i]=true;  방문처리
                        q.add(i);  큐에 추가
                    }
                }   
            }
    }

 

 :  System.out.println("sad");  while문 다 돌았는데도 종료가 안되는거면 sad
  


 

 

이제 풀어보러 갈께요 :)

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

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