송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.
상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.
편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)
각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).
다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)
송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)
출력
각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.
풀이
public class Main {
static int N;
static final int distance = 1000;
static Queue<Integer> queue;
static int[][] field;
static boolean[] visited;
static StringTokenizer st;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T-- > 0){
queue = new LinkedList<>();
N = Integer.parseInt(br.readLine());
visited = new boolean[N+2];
field = new int[N+2][2];
//초기 설정
for (int i=0; i<N+2; i++){
st = new StringTokenizer(br.readLine());
field[i][0] = Integer.parseInt(st.nextToken());
field[i][1] = Integer.parseInt(st.nextToken());
if (getDistance(field[i][0], field[i][1], field[0][0], field[0][1]) <= distance){
queue.offer(i);
visited[i] = true;
}
}
BFS();
if (visited[N+1]) {
sb.append("happy").append("\n");
} else {
sb.append("sad").append("\n");
}
}
System.out.println(sb.toString());
}
static int getDistance(int x1, int y1, int x2, int y2){
return Math.abs(x2-x1) + Math.abs(y2-y1);
}
static void BFS(){
while (!queue.isEmpty()){
int now = queue.poll();
for (int i=1; i<N+2; i++){
if (!visited[i] && getDistance(field[i][0], field[i][1], field[now][0], field[now][1]) <=distance){
queue.offer(i);
visited[i] = true;
}
}
}
}
}해설
기존 BFS문제를 풀 때 늘 좌표에 Queue를 이용해서 풀다보니 이 문제도 자연스레 그렇게 문제를 들어가다가
OOME에 막혀서 다른 풀이를 찾아보다가 그래프를 이용한 풀이를 보고 깜짝 놀란 문제였다.
물론 배열로 풀어도 상관없다.
다른 블로그에서 list를 이용한 풀이를 많이 설명했으므로, 배열을 이용한 풀이로 설명한다.
리스트를 이용한 풀이든, 배열을 이용한 풀이든 핵심은 다음과 같다.
- 맥주를 마시기 전에 집에서 갈 수 있는 편의점은 큐에 넣는다.
- 편의점을 저장할 수 있는 배열을 만든다.
상세한 코드 설명은 다음과 같다.
먼저 메인 함수를 보자.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T-- > 0){
queue = new LinkedList<>();
N = Integer.parseInt(br.readLine());
visited = new boolean[N+2];
field = new int[N+2][2];
//초기 설정
for (int i=0; i<N+2; i++){
st = new StringTokenizer(br.readLine());
field[i][0] = Integer.parseInt(st.nextToken());
field[i][1] = Integer.parseInt(st.nextToken());
if (getDistance(field[i][0], field[i][1], field[0][0], field[0][1]) <= distance){
queue.offer(i);
visited[i] = true;
}
}
BFS();
if (visited[N+1]) {
sb.append("happy").append("\n");
} else {
sb.append("sad").append("\n");
}
}
System.out.println(sb.toString());
}테스트 케이스 T를 받아서 T가 줄어들때까지 케이스를 돌린다.
가장 중요한건 [N+2][2]의 정수형 이차 배열 구조를 가진 field와, [N+2]의 불린형 일차원 배열인 visited를 선언해주는 것이다.
물론 x,y좌표를 담는 point class와 ArrayList<Point>를 만들어서 나중에 get으로 뽑아도 상관없다.
그리고 시작점과 비교해서 맨해튼 거리가 1000 이하인 편의점에 대해 큐에 넣고, visited로 처리해준다.
마지막에 BFS 함수를 돌리고, visited[N+1]로 펜타포트에 갈 수 있는지 / 없는지를 조사하고 append한다.
static int getDistance(int x1, int y1, int x2, int y2){
return Math.abs(x2-x1) + Math.abs(y2-y1);
}
static void BFS(){
while (!queue.isEmpty()){
int now = queue.poll();
for (int i=1; i<N+2; i++){
if (!visited[i] && getDistance(field[i][0], field[i][1], field[now][0], field[now][1]) <=distance){
queue.offer(i);
visited[i] = true;
}
}
}
}getDistance는 맨해튼 거리를 구하는 함수, 그리고 BFS는 단순하게 큐에 있는 편의점을 뽑아서 다음 편의점과 거리가 1000 미만이면 새로 큐에다가 추가해주면 된다.