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

0. 문제 주소

 

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

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

 

 

1. 풀이

 

사실 DFS 카테고리에서 고른게 아니었으면 조금 헤맸을 수도 있었을 문제. 

배열은 총 3개를 사용했다.

pii pos[MAX];
int d[MAX][MAX];
bool visited[MAX];

정수 좌표를 받는 pair<int, int>배열 pos,

플로이드-와샬때처럼 d[i][j] = i ~ j 사이의 거리(taxi metric),

DFS에 필요한 visited 배열

 

단순하게 생각해서 어떤 편의점에서 다른 지점으로 이동할 때, 50m 당 맥주 1병 * 20병이 최대이므로

거리가 1000m 이하인 곳을 인접한 곳으로 생각하고 DFS를 돌렸다.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define pii pair<int, int>
#define MAX 105

using namespace std;

int T;
int n;
pii pos[MAX];
int d[MAX][MAX];
bool visited[MAX];

int dist(pii a, pii b){
    int ai = a.first, aj = a.second, bi = b.first, bj = b.second;
    return (abs(ai - bi) + abs(aj - bj));
}

void DFS(int a){
    visited[a] = true;

    for (int i=0;i<=n+1;i++){
        if (i == a) continue;
        if (!visited[i] && d[a][i] <= 1000) DFS(i);
    }
}

int main(){DFS(0);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &T);
    for (int x=0;x<T;x++){
        memset(d, 0, sizeof(d));
        memset(visited, 0, sizeof(visited));
        scanf("%d", &n);
        int i_s, j_s, i_e, j_e;
        scanf("%d %d", &i_s, &j_s);
        pos[0] = pii(i_s, j_s);
        for (int i=1;i<=n;i++){
            int a, b;
            scanf("%d %d", &a, &b);
            pos[i] = pii(a, b);
        }
        scanf("%d %d", &i_e, &j_e);
        pos[n+1] = pii(i_e, j_e);
        for (int i=0;i<=n+1;i++){
            for (int j=0;j<=n+1;j++){
                if (i == j) continue;
                d[i][j] = dist(pos[i], pos[j]);
            }
        }

        DFS(0);

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