BOJ9205 / 맥주 마시면서 걸어가기

문제 요약

집에서 페스티벌까지 맥주를 마시며 가려고 한다.

맥주는 한 번에 1000미터를 이동할 수 있을만큼만 들고다닌다.

편의점에서 맥주를 충전할 수 있다.

집에서 페스티벌까지 맥주가 떨어지지 않고 갈 수 있을지 없을지 구하라.

 

입력

첫째줄에 테스트 케이스의 개수 t가 주어진다. (t <= 50)

각 테스트 케이스의 첫 줄에는 편의점의 개수 n이 주어진다. (0 <= n <= 100)

다음 n+2 줄에는 각각 집, 편의점(n개), 페스티벌의 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (-32768 <= x, y <= 32767)

도시는 직사각형 모양으로 생겼고 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이다. (맨해튼 거리)

 

 

출력

각 테스트 케이스에 대해서 맥주가 떨어지지 않으면 "happy", 맥주가 중간에 떨어지면 "sad"를 출력한다.

 

예제 입력

2

2

0 0

1000 0

1000 1000

2000 1000

2

0 0

1000 0

2000 1000

2000 2000

 

예제 출력

happy

sad

 

// https://www.acmicpc.net/problem/9205
// 20.8.13. ventania1680
package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ9205 {
    public static void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        Stack<int[]> s = new Stack<>();
        while(t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st;
            int[][] loc = new int[n + 2][2];
            for (int i = 0; i < n + 2; i++) {
                st = new StringTokenizer(br.readLine());
                loc[i][0] = Integer.parseInt(st.nextToken());
                loc[i][1] = Integer.parseInt(st.nextToken());
            }

            if (Math.abs(loc[0][0] - loc[n + 1][0]) + Math.abs(loc[0][1] - loc[n + 1][1]) <= 1000) {
                sb.append("happy\n");
                continue;
            } else {
                boolean[] visited = new boolean[n + 2];
                Arrays.fill(visited, false);
                s.clear();
                s.push(new int[] {0, loc[0][0], loc[0][1]});
                int[] tmp = new int[3];
                while(!s.empty()) {
                    tmp = s.pop();
                    if (tmp[0] == n + 1)
                        break;
                    if (visited[tmp[0]])
                        continue;
                    visited[tmp[0]] = true;
                    for (int i = 1; i <= n + 1; i++) {
                        if (visited[i])
                            continue;
                        if (Math.abs(tmp[1] - loc[i][0]) + Math.abs(tmp[2] - loc[i][1]) <= 1000)
                            s.push(new int[] {i, loc[i][0], loc[i][1]});
                    }
                }
                if (tmp[0] == n + 1)
                    sb.append("happy\n");
                else
                    sb.append("sad\n");
            }
        }
        System.out.print(sb.toString());
    }
}

 

출발점에서 도착점까지 가는 모든 경로 중에서 각 노드 사이의 거리가 1000 이하인 경로가 존재하는지를 판단하는 문제.

 

DFS, BFS, 플루이드 워셜 알고리즘 등으로 풀 수 있으며, 위 코드에서는 DFS를 사용했다.

 

스택 s, 불리언 배열 visited, 정수 배열 loc을 사용했다.

 

visited 배열에는 해당 편의점을 방문했는지 여부를 저장하고, loc 배열에는 [0]집, [1 : n] 편의점, [n + 1]페스티벌의 좌표를 각각 저장했다.

 

최초에 집에서 페스티벌까지 편의점을 거치지 않고 갈 수 있는지를 판단한다.

 

바로 갈 수 없다면 스택에 집(출발점)의 좌표를 넣고 스택이 비거나 페스티벌에 도착할 때까지 DFS로 경로를 찾는다.

 

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

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

https://github.com/ventania1680/algorithm/blob/fc50e6cd8cd0afff4a8ab1d3fe210e580a9602dd/Algorithm/src/BOJ/BOJ9205.java

ventania1680/algorithm