[알고리즘]맥주 마시면서 걸어가기/python (BFS)

✏️문제:

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

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

 

---

✏️문제풀이(실패):

처음에는 다음과 같이 생각했었다.

1. 상근이네 집과 가까운 순으로 편의점을 정렬

2. 만약 편의점이 없다면 상근이네 집~페스티벌 까지 거리가 1000을 초과하는지 안하는지 검사

3. 정렬된 편의점 순으로 탐색

       - 현재의 좌표(처음은 상근이네 집)에서 페스티벌까지의 거리가 1000이내이면 'Happy'

       - 그렇지 않다면 다음 편의점 좌표로 이동 (만약 다음 편의점 까지의 거리가 1000을 초과하면 'sad)

 

이렇게 했더니 '틀렸습니다.'가 나왔다.

bfs 카테고리에 있는 문제를 선택했기에 bfs로 풀어야 한다는 것을 알고 있었지만, 집과 편의점 사이가 거리가 가까운 순으로 정렬한다면 굳이 bfs로 풀지 않아도 된다고 생각했었다.

하지만!!! 다음과 같은 상황이라면 틀리게 된다는 것을 알게되었다.

- 상근이네 집이 (0,0)이 아님

- 총 편의점이 2곳 (가정)

           - 상근이네 집에서 가장 가까운 편의점:

                           * 상근이네 보다 페스티벌 장소로 부터 더 멈

                           * 다른 편의점과는 1000m를 초과하고, 당연히 페스티벌 장소와도 1000m를 초과함

 

          - 상근이네 집에서 2번째로 가까운 편의점:

                           * 상근이네 보다 페스티벌 장소로부터 더 가까움

                           *상근이네 집과 페스티벌 장소 두 곳과 모두 1000m 이내임

 

이런 상황이라면 나의 알고리즘은 상근이네 집과 가장 가까운 편의점에 들렀다가 'sad'가 나올 것이다.....!!ㅠㅠㅠ

 

👩‍💻결과코드(실패):

def distance(x1, y1, x2, y2):
    return abs(x1-x2) + abs(y1-y2)
t = int(input())
for _ in range(t):
    store_num = int(input()) # 편의점 갯수

    sx, sy = map(int,input().split()) # 집 좌표

    store=[]
    for i in range(store_num): # 편의점 좌표
        x, y = map(int,input().split())
        store.append([x+y,x,y])
    store.sort()

    ex, ey = map(int, input().split()) # 페스티 좌표

    x, y = sx, sy
    result = 'happy'

    # 편의점이 없을 때
    if store_num==0:
        if distance(x, y, ex, ey) > 1000:
            print('sad')
            break
        else:
            print('happy')
            break

    # 편의점이 1개 이상일 때
    for i in range(store_num):
        if distance(x, y, ex, ey)<=1000:
            break
        d=distance(x, y, store[i][1], store[i][2])
        #print("{}번째 일때 거리는{}".format(i, d))
        if d>1000:
            result='sad'
            break
        else:
            x, y = store[i][1], store[i][2]
    print(result)

 

 

✏️ 문제풀이(성공):

- 아이디어: bfs로 해결

happy인지 sad인지만 판단하면 된다.

맨처음 q에 상근이네 집 좌표를 넣고 집과 1000m이내 있는 편의점의 좌표를 q에 넣는다.

q에 있는 좌표를 하나씩 꺼내면서 페스티벌 좌표와 1000m이내이면 happy, 아니면 꺼낸 좌표와 1000m 이내에 있는 편의점 좌표를 q에 집어넣는다. 이때 q에 이미 집어넣은 좌표는 또 집어넣지 않는다.

이렇게 진행하면 1000m이내에로 맥주를 마시면서 갈 수 있는 곳들은 다 지나가게 된다.

 

 

👩‍💻결과코드(성공):

from collections import deque

def bfs():
    q = deque()
    q.append((sx, sy))
    visited=[0]*store_num

    while q:
        x, y = q.popleft()
        if abs(x-ex) + abs(y-ey) <=1000:
            return "happy"

        for i in range(store_num):
            if visited[i]==0:
                nx, ny = store[i]
                if abs(nx-x) + abs(ny-y)<=1000:
                    q.append((nx,ny))
                    visited[i]=1
    return "sad"





t = int(input())
for _ in range(t):
    store_num = int(input()) # 편의점 갯수
    sx, sy = map(int,input().split()) # 집 좌표
    store=[]
    for i in range(store_num): # 편의점 좌표
        x, y = map(int,input().split())
        store.append((x,y))
    ex, ey = map(int, input().split()) # 페스티 좌표
    print(bfs())