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

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

문제 링크

문제 링크 : https://www.acmicpc.net/problem/9205

문제 접근

송도에 사는 상근이가 락 페스티벌에 가려고 하는데 무조건 맥주를 마시면서 갈 수 있다고 합니다.

아무래도 제가 또 락을 좋아해서 짤을 올리고 싶었습니다….

아무튼 최대 맥주 20병을 들고 다닐 수 있습니다. 1병당 맨해튼 거리로 50m를 갈 수 있다고 합니다. 총 20병에 맥주가 다 채워진 경우라면 1000m를 갈 수 있습니다. 편의점의 좌표가 주어지고, 각 편의점에 들린다면 맥주를 다 채울 수 있습니다.

맨해튼 거리와 유클리드 거리

맨해튼 거리를 모르시는 분들도 있을 수 있다고 생각합니다. 이는 유클리드 거리와 다른 개념의 거리라고 할 수 있는데, 유클리드 거리는 좌표평면에서 두 점 사이 최단 직선의 길이라고 생각할 수 있습니다. 즉 직관적인 거리라고 할 수가 있습니다. 여담으로 유클리드 기하학은 고전 기하학이라고도 부르기도 합니다.

각설하고, 맨해튼 두 점 사이 최단 직선의 길이가 아닌, 계(system)의 여러개의 축의 좌표의 변위들의 합입니다. 말을 제가 어렵게 썼는데, 2차원 공간에서 두 점 사이 수평 변위와 수직 변위의 합이라고 보면 됩니다. 이러한 맨해튼 거리는 A* 알고리즘이나, AI에서 heuristic(추정치)으로 사용됩니다.

[출처 : https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC]
맨해튼 거리에 대해 이해했으니 문제로 돌아가봅시다.

이 문제의 핵심은

1) 맥주 1병당 거리가 중요한 것이 아닌, 나의 현재 위치에서 20병x50m=1000m 내부 락 페스티벌에 도착하거나, 편의점에 으로 갈 수 있는가?

2) 최단 경로를 찾는 것이 아닌 그냥 도착 여부만 판단

에 초점을 둬야 합니다. 즉, 1m마다에 대해서 판단하지 않아도 된다는 의미입니다.

그렇다면 현재 시점에서 락페(락페스티벌인데 이하 락페라고 하겠습니다..)까지 점점 거리가 가까워지는 편의점만 가면 되지 않을까라는 생각을 할 수 있는데, 이는 optimal하지 않은 해가 될 수 있습니다. 점점 가까워지는 곳으로 가다가, 거리가 살짝 모자랄 수 있는 경우가 있을 수 있기 때문입니다.

요약하자면, 나의 현재 위치에서 락페에 도착할 수 있는지, 가능하다면 happy(이 경우 현재 위치에서 락페까지의 맨해튼 거리가 1000이하인 경우입니다)를 출력. 만약 불가능하다면 갈 수 있는 편의점을 다 탐사하고, 다음 편의점으로 이동합니다. 모든 경우에서, 도착하지 못한다면 sad를 출력하면 되는 문제입니다.

결국 백트래킹 문제입니다.

소스 코드

import sys

dict={}
def manhattan_distance(x1,y1,x2,y2) : 
    return (abs(x1-x2) + abs(y1-y2))

def back_tracking(pos_x,pos_y) :
    global dest_x,dest_y,convenience_stores,answer,answer_flag 
    
    if answer_flag :
        return
    
    if manhattan_distance(pos_x,pos_y,dest_x,dest_y)<=1000 :
        answer=True
        answer_flag=True
        return
    
    for convenience_store in convenience_stores:
        con_pos_x=convenience_store[0]
        con_pos_y=convenience_store[1]
        md=manhattan_distance(pos_x,pos_y,con_pos_x,con_pos_y) #md:manhattan distance
        if md<=1000 and not dict[convenience_store]:
            dict[convenience_store]=True
            back_tracking(con_pos_x,con_pos_y)     
        
t=(int)(input())

for _ in range(t) : 
    n=(int)(input())
    start_x, start_y = map(int,sys.stdin.readline().split())
    answer=False
    answer_flag=False
    convenience_stores=[]
    for j in range(n) : 
        pos_x, pos_y = map(int,sys.stdin.readline().split())
        convenience_stores.append((pos_x,pos_y))
        dict[(pos_x,pos_y)]=False
    dest_x,dest_y = map(int,sys.stdin.readline().split())
    back_tracking(start_x,start_y)
    if answer:
        print("happy")
    else :
        print("sad")

방문한 편의점은 재방문하지 않도록 dictionary(c++에선 map에 대응됩니다)에 key로 편의점의 좌표를 저장하고, value로 방문 여부(True/False)를 저장하였습니다.

마무리하며

이 문제를 보고 올해는 락페에 꼭 가겠다는 생각을 했습니다…..