[Unsolved][JAVA] 백준 9205 맥주 마시면서 걸어가기

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

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

 

1. 서론

 

문제 유형이 아예 감이 안 와서 바로 블로그를 찾아본 문제. bfs로 푸는 방법이 있고 플로이드 워샬로 푸는 방법이 있다고 한다. 나는 블로그를 보고 플로이드 워샬로 풀었고 나중에 bfs로도 풀어야지. (안 풀겠지만)

 

2. 문제 풀이

 

상근이, 편의점, 락 페스티벌, 각각의 좌표가 주어진다. 상근이가 락 페스티벌 장에 도착하기까지 50m마다 맥주 한 병을 마셔야 한다. 맥주의 현재 재고는 20개이다. 그리고 이동 중간에 경유할 수 있는 편의점에서 맥주를 다시 최대 20개까지 얻을 수 있다. 이때 상근이가 락 페스티벌에 도착할 수 있는가, 없는가의 여부를 구하는 문제다. 맥주가 모자라면 도착하지 못하고, 맥주가 떨어지기 전에 편의점에서 맥주를 다시 살 수 있다면 락 페스티벌장까지 잘 도착할 수 있다. 

 

https://steady-coding.tistory.com/97

[BOJ] 백준 9205번 : 맥주 마시면서 걸어가기 (JAVA)

이 블로그를 보고 풀이법을 알게 되었다.(BFS 코드도 있음)

 

내가 어렵게 생각했던 포인트는 이거다.

 

1. 좌표가 음수도 있다. (2차원 배열에는 음수가 없는데??)

2. 중간에 편의점이 있고 맥주가 떨어지면 사야한다. (떨어졌는지 안 떨어졌는지, 몇 병 사야 하는지 어떻게 체크하지?)

 

1번에 대해서는 2차원 배열로 우리가 생각하는 것처럼 일반적으로 map을 만들어서 이동하는 문제가 아니었기 때문에 해결이 되었다.

2번은 그렇게 크게 고려해야 할 상황이 아니었다... 그냥 가지고 있는 맥주 내에서 다음 편의점까지 이동할 수 있는가? 정도만 체크하면 된다.

 

*플로이드 워샬 알고리즘이란? 

https://sskl660.tistory.com/61

[Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

 

플로이드 워샬 알고리즘에 따르면 이렇다.

문제의 2번째 케이스

 

0 0
1000 0
2000 1000
2000 2000

 

의 경우

 

	창근	편의점(1)	편의점(2)	락 페스티벌
창근	true	true	false	false
편의점(1)	true	true	false	false
편의점(2)	false	false	true	true
락페스티벌	false	false	true	true

 

창근이와 락페스티벌이 false이므로 sad가 출력되는 것이다!!

 

창근이의 집이 출발지이고 편의점 두 곳이 경유지, 그리고 락 페스티벌 장소가 도착지로 보고 각각 장소에 도착할 수 있는지 없는지를 조건을 줘서 확인한 후 boolean 배열로 체크해줬다. 거리가 얼마나 걸리는지 숫자는 중요하지 않기 때문에 여부만 확인하기 위해서 boolean 타입을 사용했다.

 

중요한 것은 이 조건인데 맥주가 20개가 있고 50m마다 필요하므로 두 좌표의 맨해튼 거리를 계산했을 때 20*50, 즉 1000보다 작거나 같은지를 체크해줘서 배열을 완성했다.

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

	static int n;
	static boolean[][] visit;
	static List<Point> list;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());
        for (int p = 0; p < t; p++) {
        	list = new ArrayList<Point>();
        	n = Integer.parseInt(br.readLine());
        	
        	for (int i = 0; i < n + 2; i++) {// 상근, 편의점(n), 락페 좌표
        		StringTokenizer st = new StringTokenizer(br.readLine());
        		int x = Integer.parseInt(st.nextToken());
        		int y = Integer.parseInt(st.nextToken());
        		list.add(new Point(x, y));
        	}
        	
        	visit = new boolean[n + 2][n + 2]; //상근, 편의점(n),락페 각 장소간의 도착 여부 저장
         	
        	//맥주가 있을 때 갈 수 있는 거리 방문 처리
        	for (int i = 0; i < n + 2; i++)
        		for (int j = 1; j < n + 2; j++)
        			if (distance(list.get(i), list.get(j)) <= 1000) //맥주 20개 x 50m 
        				visit[i][j] = visit[j][i] = true;
        	
        	floyd();

        	sb.append(((visit[0][n + 1]) ? "happy" : "sad") + "\n");
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static int distance(Point p1, Point p2) { //맨해튼 거리
    	return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }
    
    public static void floyd() { //플로이드 워샬, 가장 짧은 거리 갱신, 경유지 -> 출발지 -> 목적지
    	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 (visit[i][k] && visit[k][j])
    					visit[i][j] = true;
    }
}

 

원래의 플로이드 워샬 코드는 이동한 거리를 저장하고 최솟값을 구해야 하기 때문에 위의 코드보다는 복잡하지만 이 문제는 여부만 알면 되기 때문에 간단하다.

 

플로이드 워샬을 돌리기 위해서는 한 번 이동했을 때의 값이 미리 세팅되어 있어야 하므로 (비교해서 값을 내야 하기 때문에) 두 좌표의 맨해튼 거리가 1000m 안인지 체크하고 값을 세팅해줬다.

 

경유지, 출발지, 목적지 순서로 for문을 돌려야 한다는디... for문 기준으로 i가 출발지, j가 목적지, k가 경유지이다. 그래서 visit[i][k] , visit[k][j]를 보고 visit[i][j]를 결정하게 된다. (나도 잘 모름 그냥 외움)

 

위의 표를 보면 마지막이 visit 배열의 마지막 값이 창근이와 락페스티벌의 값, 즉 출발지~목적지 가능 여부를 나타내기 때문에 visit[0][n + 1]의 값이 정답이 된다.