문제 링크
주의사항
- 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미터 이내가 아닐 때
}
}
'백준' 카테고리의 다른 글
[백준] 알고리즘 분류(두 포인터,JAVA)13144번, List of Unique Numbers (0) | 2023.03.21 |
---|---|
[백준] 알고리즘 분류(누적합,JAVA)17305번, 사탕 배달 (0) | 2023.03.10 |
[백준] 알고리즘 분류(다이나믹 프로그래밍,JAVA)9084번, 동전 (0) | 2023.02.25 |
[백준] 알고리즘 분류(그래프 이론,JAVA)4485번, 녹색 옷 입은 애가 젤다지? (0) | 2023.02.25 |
[백준] 알고리즘 분류(수학,JAVA)1016번, 제곱 ㄴㄴ 수 (0) | 2023.02.22 |
댓글