[백준] Gold V. 맥주 마시면서 걸어가기

 

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

 

 

사용 알고리즘

• 그래프 탐색
• BFS

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static int t, n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());

        for(int k = 0; k < t; k++) {
            n = Integer.parseInt(br.readLine());

            List<int[]> location = new ArrayList<>();
            boolean [] visited = new boolean[n + 2];
            List<List<Integer>> graph = new ArrayList<>();

            for(int i = 0; i < n + 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                location.add(new int[]{x, y});
            }


            for(int i = 0; i < n + 2; i++){
                graph.add(new ArrayList<>());
            }

            for(int i = 0; i < n + 2; i++){
                for(int j = i + 1; j < n + 2; j++) {
                    if (possible(location.get(i), location.get(j))) {
                        graph.get(i).add(j);
                        graph.get(j).add(i);
                    }
                }
            }

            if (bfs(graph, visited)) sb.append("happy");
            else sb.append("sad");

            if (k < t - 1) {
                sb.append("\n");
            }
        }

        System.out.print(sb);
    }

    public static boolean bfs(List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        while(!queue.isEmpty()) {
            int node = queue.poll();
            for(int next : graph.get(node)) {
                if (visited[next]) continue;

                if (next == n + 1) return true; // 간선의 개수가 n + 1개, 즉 끝점에 도달했다는 뜻
                visited[next] = true;
                queue.add(next);
            }
        }
        return false;
    }

    public static boolean possible(int [] x, int [] y) {
        if ((Math.abs(x[0] - y[0]) + Math.abs(x[1] - y[1])) <= 1000) return true;
        return false;
    }
}

 

회고

 

그래프에 익숙하지 않아서 까다로운 문제였다. 

 

일단, 해당 좌표를 그래프로 변환하는 과정에서 거리가 1000 아래일 때만 변환해주는 생각을 하지 못했다.

0 0
1000 0
1000 1000
2000 1000

 

이렇게 예제가 주어질 때,

0 -- 1 -- 2 -- 3

 

이런식으로 전부 이어진 형태가 된다.

 

반면에,

0 0
1000 0
2000 1000
2000 2000

 

0 -- 1

2 -- 3

 

1, 2 사이의 거리가 1000이 넘기 때문에 이렇게 나눠져서 그래프가 형성된다.

 

문제에서 (0, 0)과 같은 좌표를 List<int []> position에 한번에 묶어서 담아주고, 이중 포문을 돌면서 거리가 1000이 넘는지 체크한다.

for(int i = 0; i < n + 2; i++){
    for(int j = i + 1; j < n + 2; j++) {
        if (possible(location.get(i), location.get(j))) {
            graph.get(i).add(j);
            graph.get(j).add(i);
        }
    }
}

 

이중 for문을 왜 도는지에 대해서 좀 헷갈렸는데, 쉽게 이야기 해서 1 -- 2 뿐만 아닌 1 -- 3, 1 -- 4와 같은 모든 노드에 대해서 이어질 수 있는지 체크해서 그렇다. 

 

bfs가 true인 조건은, 

next == n + 1

 

인데, next (현재 보고 있는 노드)가 3이라면, 끝까지 도달했다는 뜻 이므로 true를 리턴해 준다.

 

2번째 예시같은 경우, next를 출력해보면 1이기 때문에 false를 리턴해준다.

 

 

로직을 봤을때 그렇게 어렵지 않은 문제인데, 많이 풀어봐야겠다.