[BOJ] 9205 맥주 마시면서 걸어가기 - JAVA

1. 문제

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

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

---

2. 풀이

공통변수

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st;
Queue<int[]> queue = new ArrayDeque<>();

 

입력(테스트케이스 당)

맨 처음 값은 집 위치이므로 저장필요없이 queue에 넣었다.

나머지는 페스티벌 장소까지 N+1칸 배열에 담았다.

3칸을 만든 이유는 가로, 세로, 방문여부까지 한번에 처리하기 위해서다.

int N = Integer.parseInt(in.readLine());
st = new StringTokenizer(in.readLine());
queue.offer(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});//집

int[][] position = new int[N+1][3];

for(int n=0;n<=N;n++){
   st = new StringTokenizer(in.readLine());
   position[n][0] = Integer.parseInt(st.nextToken());
   position[n][1] = Integer.parseInt(st.nextToken());
}

 

탐색 및 결과 출력

position[n][2]번은 방문여부표시하는 위치이므로 그 위치를 이미 방문한 적 있다면 다시 방문하지 않는다.

x위치차이 + y위치차이가 1000을 넘으면 안되므로 넘어간다. (맥주 50미터 * 20개 = 1000미터)

그 외의 경우는 queue에 넣고 방문표시도 한다.

 

반복문이 모두 끝난 뒤 position[N][2] (= 페스티벌장소 방문여부)가 0이 아니어야 집에서부터 페스티벌까지 도착할 수 있는 테스트케이스다. 

0이 아니라면 happy, 0이라면 sad를 출력한다.

int[] pos;
while(!queue.isEmpty()){
   pos = queue.poll();

   for(int i=0;i<=N;i++){
      if(position[i][2]!=0) continue;
      if(Math.abs(pos[0]-position[i][0])+Math.abs(pos[1]-position[i][1]) > 1000) continue;
      queue.offer(position[i]);
      position[i][2] = -1;//방문표시
   }

}

if(position[N][2]!=0) sb.append("happy\n");
else sb.append("sad\n");

---

3. 결과