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

# 주소

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

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

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;

public class Main {
    static int n, m, x, y;
    static int arr[][];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        while (n-- > 0) {
            m = scan.nextInt();
            arr = new int[2][m + 2];
            int[][] ans = new int[m + 2][m + 2];
            for (int i = 0; i < m + 2; i++) {
                arr[0][i] = scan.nextInt();
                arr[1][i] = scan.nextInt();
            }
            int sum = 0;
            for (int i = 0; i < m + 2; i++) {
                for (int j = 0; j < m + 2; j++) {
                    sum = 0;
                    sum += Math.abs(arr[0][i] - arr[0][j]);
                    sum += Math.abs(arr[1][i] - arr[1][j]);
                    if (sum <= 1000) {
                        ans[i][j] = 1;
                        ans[j][i] = 1;
                    }
                }
            }
            boolean[] visit = new boolean[m + 2];
            visit[0] = true;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            while (!queue.isEmpty()) {
                int now = queue.poll();
                for (int i = 0; i < m + 2; i++) {
                    if (ans[now][i] == 1) {
                        if (!visit[i] == true) {
                            visit[i] = true;
                            queue.offer(i);
                        }
                    }
                }
            }
            if (visit[m + 1]) {
                System.out.println("happy");
            }else{
                System.out.println("sad");
            }
        }
    }
}

arr를 2차원으로 배열 받아야 하는 문제입니다.

처음엔 arr의 각 좌표마다 1값을 삽입하여 풀려고 했으나 그렇게 하게 되면 배열 값이 너무나도 커지므로 x의 값은 arr[0][i], y값은 arr[1][i]값에 넣는 것이 타당합니다.

따라서 들어오는 arr값을 모두 삽입하고 이중 for문을 이용하여 실제 거리를 구해봅니다.

이것은 이중 for문으로 할 것입니다.

 

문제에서 삽입되는 좌표 값이 오름차순으로 들어오는 것인지에 대한 자세한 명세가 안되어 있기 때문에 좌표설정은 랜덤하게 입력됨을 알아야 합니다.

따라서 sum값을 구해보면 sum 은 x 값은 Math.abs(arr[0][i] - arr[0][j])로 하고 y값은 Math.abs(arr[1][i] - arr[1][j])로 설정합니다.

왜 이중 for문으로 sum값을 구하는 것일까요?

 

자 이유는 간단합니다.

arr[0][i]값과 arr[0][j]값의 차. 그러니까 해당 i의 값과 이것을 포함하여 모든 인덱스의 값인 j에 대한 값을 각각 x, y에 대해 구하여 더한 그 sum이 "맨해튼 거리"라는 기법의 x,y 구하는 방식입니다.

문제에서도 설명되어 있듯이 맨해튼 거리는 x의 차 + y의 차를 더한 것이기 때문에 따로 실제 이동 거리를 구하는 것이 아닌, x와 y에 대해서만 구하면 됩니다.

그러므로 구해진 sum이 1000보다 작거나 같으면 ans의 해당 인덱스를 1로 바꿀 것입니다.

왜 이렇게 할까요?

 

이것도 이유는 간단합니다.

우리가 푸는 문제는 bfs문입니다.

이 bfs는 너비우선탐색이기 때문에 인접해 있는 값을 찾아서 계속해서 파고 들어가며 최종적인 목적지에 도달하는 것이 목표입니다.

따라서 ans를 모두 1로 바꾸고 난 뒤 0에서의 인덱스일 때 ans가 1일 때부터 시작하여 (만약 0의 위치에서 0으로부터 거리가 하나라도 1000이하인 곳이 있으면 인접해 있는 것이므로 해당 인덱스로 이동) 인접해 있는 인덱스로 이동합니다.

boolean[] visit new boolean[m + 2];
visit[0] = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
while (!queue.isEmpty()) {
    int now = queue.poll();
    for (int i = 0; i < m + 2; i++) {
        if (ans[now][i] == 1) {
            if (!visit[i] = true) {
                visit[i] = true;
                queue.offer(i);
            }
        }
    }
}

그래서 여길 보시면 해당 Queue의 visit을 true로 설정하고 queue에 0을 offer하여 본격적으로 여느 bfs문처럼 queue를 가동합니다.

그리고 꺼내온 queue의 현재점을 now로 잡고 for문을 이용하여 계속해서 ans[now][i]가 1인 곳이 있는지. 만약 있는데 방방문하지 않은 지점이면 그것을 true로 바꾸고 queue에 다시 i를 넣음으로써 모든 인접해 있는 ans를 탐색할 수 있습니다.

하지만 불행하게도 도착지점의 visit을 출력했을 때 만약 false라면 도착지점까지 인접해 있는 ans가 없다는 뜻이므로 sad를 출력하고 true라면 happy를 출력합니다.

 

감사합니다.