문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1600번 말이 되고픈 원숭이 (5) | 2018.07.18 |
---|---|
백준 1939번 중량제한 (2) | 2018.07.18 |
백준 2718번 타일 채우기 (0) | 2018.07.17 |
백준 7578번 공장 (0) | 2018.07.17 |
백준 6549번 히스토그램에서 가장 큰 직사각형 (2) | 2018.07.16 |