백준 9205 맥주 마시면서 걸어가기(dfs)

https://www.acmicpc.net/problem/9205

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

#include <iostream>
#include <vector>

using namespace std;
const int MAX=102;
int n;
vector<pair<int, int>> p;
vector<int> graph[MAX];
bool visited[MAX];

bool distance(pair<int, int> p1, pair<int, int> p2)
{
    int dis = abs(p1.first - p2.first) + abs(p1.second - p2.second);
    if (dis <= 1000)
        return true;
    else
        return false;
}

void dfs(int x)
{
    visited[x] = true;
    for (int i = 0; i < graph[x].size(); i++)
    {
        if (!visited[graph[x][i]])
            dfs(graph[x][i]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int testcase;
    cin>>testcase;
    while(testcase--){
        cin >> n;
    for (int i = 0; i < n + 2; i++)
    {
        int num1, num2;
        cin >> num1 >> num2;
        p.push_back(make_pair(num1, num2));
    }
    for (int i = 0; i < n + 2; i++)
    {
        for (int j = i + 1; j < n + 2; j++)
        {
            if (distance(p[i], p[j]))
            {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }
    dfs(0);
    if (visited[n + 1])
        cout << "happy"<<"\n";
    else
        cout << "sad"<<"\n";

        for(int i=0;i<MAX;i++){
            graph[i].clear();
            visited[i]=false;
        }
        p.clear();
    }
    
}

일단! 또 어떻게 풀어야할지 감이 잡히지 않아 jaimemin님의 코드를 또 봐버렸다.

https://jaimemin.tistory.com/709             (내 코드보다 훨씬 좋은 코드다....사실 보고 풀었기에 비슷하다.)

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

제일 중요한 것은 입력으로 들어오는 시작점, 편의점 위치, 도착지점을 모두 하나의 노드로 생각한다는 것이다.

 

그 이후 서로가 서로에게 도달할 수 있는 거리에 위치한다면 edge로 연결하고 그렇지 않다면 연결하지 않아서, 결국 dfs로 순회하였을때 어떻게든 도착지점까지 연결되어 있다면 방문한 기록이 있을 것이고 그렇지 않다면 방문한 기록이 없을 것이다.

 

각각을 노드라 생각하는 발상이 신기했다.

 

또 여기서 중요한 것은 각 노드에서 다른 노드로 연결됐는지 기록하는 graph 배열을 int형 2차원 배열이 아닌 vector형 2차원 배열로 했다는 것이다.

이렇게 되면 각 행이 가지는 열의 개수가 달라지기 때문에 유의해야한다. 이와 비슷한 형태의 문제를 풀고 기록을 남겼던 기억이 있는데 몇번 문제였는지 기억이 안난다.

 

void dfs(int x)
{
    visited[x] = true;
    for (int i = 0; i < graph[x].size(); i++)
    {
        if (!visited[graph[x][i]])
            dfs(graph[x][i]);
    }
}

각 행이 가지는 열의 개수가 다를 때 사용하는 dfs모양이 이렇다는 것을 꼭 기억해야 한다. 또한 parameter도 기존처럼 2개가 아닌 1개라는 점을 명심할 필요가 있겠다.