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

 

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

---

저는 dfs를 사용하였습니다.

DFS를 사용하는 이유: 거리가 되는 모든 방향을 탐색해야 하기 때문

https://www.acmicpc.net/board/view/86660

 

x와 y의 값이 1000(20X50) 이하이면 갈 수 있다

1000보다 크면 갈 수 없다

 

 

입력 받기

from sys import stdin
t = int(stdin.readline())

result = []
for _ in range(t):
    n = int(stdin.readline()) # 편의점 개수
    home_x, home_y = map(int, stdin.readline().split())
    store = []    
    for _ in range(n):
        store.append(list(map(int, stdin.readline().split())))
        
    festival_x, festival_y =map(int, stdin.readline().split())

 

1. 페스티벌에서 집까지

1-1. 바로 갈 수 있다 -> happy 출력

1-2. 바로 못 간다 -> 편의점을 들른다

    2.편의점을 for문으로 돌면서 집에서 편의점까지

    2-1. 바로 갈 수 있다 -> 편의점에서 페스티벌까지 갈 수 있는 루트를 찾는다

    2-2. 바로 못 간다 -> pass

 

집에서 바로 갈 수 있는 편의점 중 페스티벌까지 갈 수 있는지 DFS를 이용하여 확인한다.

# 페스티벌과 집까지의 거리 구함
x = festival_x-home_x if festival_x > home_x else home_x-festival_x
y = festival_y-home_y if festival_y > home_y else home_y-festival_y

# 맨해튼 거리(x+y)가 1000 이하이면
if x+y<=1000:
    print('happy')
else:
    hp = 'sad' # Defalut
    
    # 편의점 돌면서
    for store_x, store_y in store:
    	# 편의점과 집의 거리
        x = store_x-home_x if store_x > home_x else home_x-store_x
        y = store_y-home_y if store_y > home_y else home_y-store_y
        
        # 1000보다 작은 것만
        if x + y <= 1000:
            visited = []
            # 1000 안쪽의 편의점 들렸을 때, 편의점에서 페스티벌까지를 dfs로 판단
            res = dfs(store_x, store_y)
            if res == 1:
                hp = 'happy'
                break  
    print(hp)

 

 

DFS 함수

def dfs(now_x, now_y):
    # visit
    visited.append((now_x, now_y))
    
    # festival이랑 거리 봐 -> 되면 happy
    x = now_x-festival_x if now_x > festival_x else festival_x-now_x
    y = now_y-festival_y if now_y > festival_y else festival_y-now_y
    if x + y <= 1000:
        return True
    # 안되면 다른 편의점 가
    for s_x, s_y in store:
        if (s_x, s_y) not in visited: # 들르지 않은 곳 중
            # 지금 위치랑 편의점 위치 확인
            d_x = now_x-s_x if now_x > s_x else s_x-now_x
            d_y = now_y-s_y if now_y > s_y else s_y-now_y
        
            if d_x + d_y <= 1000:
                # 1000 되면 가
                if dfs(s_x, s_y):
                    return True # True가 한 번이라도 반환되면 상위도 다 True 
    return False

편의점에서 바로 페스티벌까지 갈 수 있는지 확인

갈 수 있다 -> True 리턴

갈 수 없다 -> 방문하지 않은 편의점 중 갈 수 있는 곳(1000이하인)을 DFS로 간다

 

실패 이유:

1. 처음에 집과 페스티벌이 바로 갈 수 있는 지 확인하지 않았다.

2. dfs가 끝나고 return True를 하지 않았다.

return True를 하는 이유: 상위 함수도 True를 받아서 탐색을 종료할 수 있도