BOJ9505 맥주 마시면서 걸어다니기

1. 문제링크 :  BOJ9505 : 맥주 마시면서 걸어다니기

2. 문제요약

 -  송도에 사는 상근이와 친구들은 맥주를 마시면서 걸어가기로함, 상근이네 집에서 출발      하여 맥주 한 박스를 들고 출발한다.
 - 맥주 한 박스에는 맥주가 20개 들어있는 상황, 이동중에 50미터에 한 병씩 맥주를 마심
 - 도착지 까지 맥주를 마시면서 가되, 중간에 맥주를 파는 편의점에서 맥주를 구매 가능하     지만 편의점에 들렸을 때 빈 병은 버리고 새 맥주병을 살 수 있음.
 - 박스에는 20병 넘게 맥주를 담을 수 없다.

 Goal : 상근이가 도착지까지 맥주를 마시면서 도착 할 수 있는가 판단하기

3. 문제풀이

 - 다양한 풀이법이 존재하겠지만 본 풀이에서는 DFS를 이용하였다.
 - 편의점이 N개 존재할때, 시작지점을 0번 노드, 편의점을 1~N 번노드, 도착지점을 N+1       번  노드라고 가정하였다.
 - 이때 DFS를 이용하여 0번 노드에서 시작하되, 20병의 맥주를 소모해서 갈 수 있는 거리      (2000) 이내에 존재하는 노드를 방문하여 최종 지점까지 방문해간다.
 - 만약 N+1 번 노드에 도달 할 수 있다면 맥주를 마시면서 도착이 가능하고 N+1번 노드       에  도달이 불가능 하다면 도착이 불가능하다.

4. 소스코드 ( C )

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    int x;
    int y;
}node;

bool result=false;

node set[102];
bool check[102];

int n;

void dfs(int m){
    check[m]=true;
    if(m==n+1)
    {
        result = true;
        return ;
    }

    for(int i=1;i<=n+1;i++){
        int distance=abs(set[i].x-set[m].x)+abs(set[i].y-set[m].y);
        if(check[i]==false&&distance<=1000){
            dfs(i);
        }
    }
}

int main(void){
    set[0].x=0;
    set[0].y=0;

    int t;
    scanf("%d",&t);

    for(int z=0;z<t;z++){
        memset(check,false,sizeof(check));
        result=false;
        scanf("%d",&n);
        for(int i=0;i<=n+1;i++){
            scanf("%d %d",&set[i].x,&set[i].y);
        }
        dfs(0);
        if(result)
            printf("happy\n");
        else
            printf("sad\n");
    }
    return 0;
}