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

www.acmicpc.net/problem/9205

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

어떻게 접근해야 하는지 어려웠던 문제이다.

관건은 편의점마다 노드 번호를 붙여서 연결 그래프를 만드는 것이 핵심이었다.

 

모든 편의점 위치를 저장한다음 각 편의점마다 접근가능한 (맨해튼거리 1000이하) 편의점을 연결리스트에 저장한다.

연결리스트를 만들었다면 bfs를 사용해서 목적지인 n+1을 방문했는지 확인한다.

참고로 dfs를 써도 방문확인이 가능하다.

#include <stdio.h>
#include <vector>
#include <string.h>
#include <math.h>
#include <queue>

using namespace std;
struct s
{
  int row, col;
};
int t, n;
int x, y;
bool visited[105];

int get_distance(const s &t1, const s &t2)
{
  return abs(t1.row - t2.row) + abs(t1.col - t2.col);
}

int main(void)
{
  scanf("%d", &t);
  while (t--)
  {
    vector<s> v;
    vector<int> v1[105];
    memset(visited, false, sizeof(visited));
    scanf("%d", &n);

    for (int i = 0; i < n + 2; i++)
    {
      scanf("%d%d", &x, &y);
      v.push_back({x, y});
    }

    for (int i = 0; i < n + 1; i++)
    {
      for (int j = i + 1; j < n + 2; j++)
      {
        if (get_distance(v[i], v[j]) <= 1000)
        {
          v1[i].push_back(j);
          v1[j].push_back(i);
        }
      }
    }
    queue<int> q;
    q.push(0);
    visited[0] = true;
    while (!q.empty())
    {
      int top = q.front();
      q.pop();

      for (auto a : v1[top])
      {
        if (visited[a])
          continue;
        q.push(a);
        visited[a] = true;
      }
    }

    if (visited[n + 1])
    {
      printf("happy\n");
    }
    else
    {
      printf("sad\n");
    }
  }
  return 0;
}