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

문제 링크입니다: https://www.acmicpc.net/problem/9205

문제 덕분에 '맨해튼 거리'라는 개념을 처음 알게 되었습니다.

맨해튼 거리는 두 좌표 사이의 거리를 'x 좌표간의 거리' + 'y 좌표간의 거리'로 표현합니다.

(https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC)

알고리즘은 아래와 같습니다.

1. 좌표를 입력 받을 때 출발점, 편의점들, 그리고 도착점의 좌표를 pair<int, int>형 배열에 입력받습니다.

2. 편의점을 방문할 때마다 맥주 20병씩 가지고 다닐 수 있기 때문에 모든 좌표들을 비교하며 맨해튼 거리로 50 * 20 즉, 1000 이내에 있는 좌표들의 인덱스를 양방향 그래프에 추가합니다.

3. 출발점의 인덱스는 0이기 때문에 출발점에 대해 DFS(Depth First Search) 알고리즘을 돌리고 도착점에 도달했는지 visited 배열을 통해 확인합니다.

4. 도달했으면 'happy' 도달하지 못했다면 'sad'를 출력합니다.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 2; //출발점, 도착점 포함

 

int N;

vector<int> graph[MAX];

bool visited[MAX];

 

//맨해튼 거리

int distance(pair<int, int> p1, pair<int, int> p2)

{

        return abs(p1.first - p2.first) + abs(p1.second - p2.second);

}

 

//전형적인 DFS

void DFS(int node)

{

        visited[node] = true;

 

        for (int i = 0; i < graph[node].size(); i++)

        {

                 int next = graph[node][i];

                 if (visited[next] == false)

                         DFS(next);

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

 

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 for (int j = 0; j < MAX; j++)

                         graph[j].clear();

                 memset(visited, false, sizeof(visited));

 

                 cin >> N;

                 vector<pair<int, int>> coord;

 

                 //출발점(0), 도착점(N + 1) 포함

                 for (int j = 0; j < N + 2; j++)

                 {

                         int y, x;

                         cin >> y >> x;

 

                         coord.push_back(make_pair(y, x));

                 }

 

                 //맥주 20병으로 갈 수 있는 거리 내에 있으면 그래프에 추가

                 for(int j=0; j<N+2; j++)

                         for(int k=j+1; k<N+2; k++)

                                 if (distance(coord[j], coord[k]) <= 50 * 20)

                                 {

                                          //양방향 그래프

                                          graph[j].push_back(k);

                                          graph[k].push_back(j);

                                 }

 

                 DFS(0);

                 //0이 출발점, N+1이 도착점이므로

                 if (visited[N + 1])

                         cout << "happy\n";

                 else

                         cout << "sad\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~