맥주 마시면서 걸어가기

문제

풀이

처음 풀었을 때 잘못 접근했던 부분이 2가지가 있었다.

1. 그리디로 접근하기 (그리디로 하면 안된다.)
집과 편의점 사이 거리 중 가장 가까운 편의점 부터 접근을 하였다.
하지만 이렇게 하면 문제점이 발생하는데
음수일 때를 생각을 해야 한다.

(TestCase)
집 => 0, 0
편의점 => -800, 0
편의점 => 1000, 0
페스티벌 => 1000, 2000

위 테스트케이스에서 가장 가까운 편의점은 (-800, 0)이지만
실제로는 (1000, 0), (1000, 2000) 경로로 가야 한다.

그래서
모든 경로를 탐색하는 BFS, DFS로 풀어야 한다.

2. 만약 맥주가 남는 상황이 생긴다면?
예제 테스트케이스에서는 1000단위로 이루어져있기 때문에 큰 문제가 없었지만
852, -951처럼 된다면 남은 맥주를 어떻게 처리할 지가 문제였다.
이 부분은 리필한 맥주와 남은 맥주를 더한 값을 처리해 주었는데

다르게 생각해야 했다.
최단거리로 갈 필요가 없기 때문에 가까운 편의점이더라도 모든 맥주를 소모한 후 편의점에 도착하여 맥주 20개를 리필하면 되는 것이였다.

이것을 고려한 답은

풀이

def solution():
    tc = int(sys.stdin.readline())

    for _ in range(tc):
        n = int(sys.stdin.readline().rstrip())

        home_row, home_col = map(int, sys.stdin.readline().split())
        store = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
        festival_row, festival_col = map(int, sys.stdin.readline().split())

        q = deque()
        q.append((home_row,home_col))
        dp = {}
        flg = False
        while q:
            cur_row, cur_col = q.popleft()

            if abs(festival_row - cur_row) + abs(festival_col - cur_col) <= 1000:
                flg = True
                break

            for store_row, store_col in store:
                dist = abs(store_row - cur_row) + abs(store_col - cur_col)

                if (store_row, store_col) in dp:
                    continue

                if dist <= 1000:
                    q.append((store_row, store_col))
                    dp[(store_row, store_col)] = 1

        if flg:
            print('happy')
        else:
            print('sad')

solution()