[ 백준 9205 ] 맥주 마시면서 걸어가기 (C++)

[문제보기]

 

[해결과정]

 1. 좌표를 저장할 배열 arr[MAX][2] 와 방문 체크할 배열 check[MAX] 준비

 2. 집(0번 순서) 부터 편의점(1부터 N까지 순서), 마지막 도착지 (N+1번 순서) 까지 입력 받음

 3. BFS()

  3-1. 좌표의 절대값 (x 비교값 + y 비교값) 이 1000 이하여야 이동가능!

 

[소스코드]

#include<iostream>
#include<queue>
#include<vector>
#include<memory.h>
#include<math.h>
using namespace std;
const int MAX = 104;
 
int n, ans;
 
int check[MAX];
int arr[MAX][2];
queue <pair<int, int>> q;
 
void bfs() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        if (x == arr[n+1][0] && y == arr[n + 1][1]) {
            ans = 1;
            return;
        }
 
        int ny, nx;
        for (int i = 1; i < n + 2; i++) {
            nx = abs(x - arr[i][0]);
            ny = abs(y - arr[i][1]);
            if (check[i] == 0 && nx + ny <= 1000) {
                check[i] = 1;
                q.push(make_pair(arr[i][0], arr[i][1]));
            }
        }
    }
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int t;
    cin >> t;
    for (int k = 0; k < t; k++) {
 
        // 초기 설정
        while (!q.empty()) q.pop();
        memset(check, 0, sizeof(check));
        memset(arr, 0, sizeof(arr));
        ans = 0;
 
        cin >> n;
        for (int i = 0; i < n + 2; i++) {
            cin >> arr[i][0] >> arr[i][1];
        }
        q.push(make_pair(arr[0][0], arr[0][1]));
        bfs();
 
        if (ans == 1) cout << "happy" << "\n";
        else cout << "sad" << "\n";
 
    }
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 1. 정말 간단한 BFS 기본 문제 중 하나다. 문제를 읽어보면 좀 꼬아놓은 부분이 있어서.. 생각이 많아지는 부분이 있다. 하지만 기본 중 기본 BFS문제였다.

 2. 구조체를 이용해서 check 처리를 했는데, 초기화가 제대로 안됐나... 계속해서 실패했다. 초기화가 문제였던 것 같다.

 

[관련 문제 혹은 비슷한 문제]

 DFS, BFS, 플로이드와샬