[BOJ/9205/C++] 맥주 마시면서 걸어가기

 

오랜만에 골드 문제를 풀어보았다.

그만큼 시간 소요도 오래 되었고 BFS를 이용해서 푸는 것은 알았지만, 적절하게 활용하는 것이 어려웠다.

 

 

거의 다 왔다고 생각하며 풀어보려고 했지만 계속 나는 런타임 에러,,

코드 자체에 문제가 있었다기 보다 코드의 흐름이 맞지 않았던 것 같다.

 

그래서 처음부터 다시 문제를 풀었다.

우선 이 문제에서 구조체를 사용했다. 내가 Java로 코테를 준비할 때도 BFS 문제는 생성자를 이용해서 풀었다.

C++도 이런 성질을 이용해서 푸는 것이 용이했다.

 

main() 함수를 먼저 작성했기 때문에 main() 함수 먼저 살펴보자

int main() {

    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);

    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cout << bfs(n) << endl;
    }

    return 0;
}

 

main() 함수에서 테스트 케이스의 개수 t를 입력받고 편의점의 개수 n을 t만큼 입력받고 있다.

BFS는 함수화를 하면 좋을 것 같다고 생각해서 n을 매개변수로 넘기는 bfs() 함수를 만들었다.

 

이때 생각했던 것이 return 값을 string으로 해서 bfs() 함수 내에 happy와 sad를 각각 반환해주는 흐름으로 짜야겠다고 생각했다.

 

그리고 구조체 부분이다.

struct pos
{
    int x;
    int y;
};
pos store[100];
pos festival;
pos home;

 

x, y 좌표 형태이기 때문에 위와 같이 코드를 짰다.

 

 

가장 중요한 BFS 함수 부분이다.

string bfs(int n) {
    fill(visited, visited + 100, false);

    cin >> home.x >> home.y;

    for (int i = 0; i < n; i++) {
        cin >> store[i].x >> store[i].y;
    }

    cin >> festival.x >> festival.y;

    queue<pair<int, int>> q;
    q.push({ home.x, home.y });

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (abs(festival.x - x) + abs(festival.y - y) <= 1000) return "happy";
        for (int i = 0; i < n; i++) {
            if (visited[i] == 1) {
                continue;
            }
            if (abs(store[i].x - x) + abs(store[i].y - y) <= 1000) {
                visited[i] = 1;
                q.push({ store[i].x, store[i].y });
            }
        }
    }
    return "sad";
}

 

우리는 bfs() 함수를 여러 번 부를 거기 때문에 fill() 함수를 통해 visited를 false로 초기화해줘야 한다.

그다음 집, 편의점, 페스티벌 좌표를 각각 입력받는다.

 

그리고 BFS를 이용하기 위해 Queue를 만들어 집의 좌표를 먼저 push 해준다.

그리고 선입선출 방식으로 하나씩 빼면서 그 값을 확인해준다.

 

우리는 큐에 두 개의 int 값을 넣고 있기 때문에  q.front().first 처럼 두 개의 값을 각각 꺼내올 수 있다.

 

이어서 abs() 함수가 등장한다.

int abs(int n) {
    if (n < 0) return -n;
    else return n;
}

 

이번 문제를 풀면서 처음 알게된 방법이다.

abs() 함수의 기능은 주어진 숫자의 절대값을 반환해주는 것이다. 

즉, 이번 코드에서는 좌표 간의 거리를 계산하는 데 사용되고 있다. 

좌표평면에서 두 점 (x1, y1)과 (x2, y2) 사이의 맨해튼 거리는 |x1 - x2| + |y1 - y2|로 계산된다.

 

이 거리가 1000이하라는 것은 현재 위치에서 페스티벌까지 맥주를 마시면서 갈 수 있다는 의미이다.

 

1000이 기준인 이유는 편의점 없이 갈 수 있는 최대 거리가 1000m이기 때문이다

 

 

전체 코드는 아래와 같다.

#include<iostream>
#include<queue>
using namespace std;
int abs(int n);
string bfs(int n);
struct pos
{
    int x;
    int y;
};
pos store[100];
pos festival;
pos home;
bool visited[100];
int main() {

    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);

    int t;
    cin >> t;

    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cout << bfs(n) << endl;
    }

    return 0;
}
int abs(int n) {
    if (n < 0) return -n;
    else return n;
}
string bfs(int n) {
    fill(visited, visited + 100, false);

    cin >> home.x >> home.y;

    for (int i = 0; i < n; i++) {
        cin >> store[i].x >> store[i].y;
    }

    cin >> festival.x >> festival.y;

    queue<pair<int, int>> q;
    q.push({ home.x, home.y });

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (abs(festival.x - x) + abs(festival.y - y) <= 1000) return "happy";
        for (int i = 0; i < n; i++) {
            if (visited[i] == 1) {
                continue;
            }
            if (abs(store[i].x - x) + abs(store[i].y - y) <= 1000) {
                visited[i] = 1;
                q.push({ store[i].x, store[i].y });
            }
        }
    }
    return "sad";
}