[백준] 9205 맥주 마시면서 걸어가기 (python 파이썬)

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

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

---

맨해튼 거리인 줄 모르고 삽질했다. 문제를 잘 읽어보자.

---

아이디어

1. 그래프 탐색

• 심플하게 맥주 20병 = 1000m라고 생각하고 1000m를 기준으로 갈 수 있는지 없는지 확인하면 된다.
• bfs를 사용하여 해결했다.

---

전체 코드

from collections import deque

def cal_distance(x, y, nx, ny):
    return abs(nx - x) + abs(ny - y)


def bfs():
    if cal_distance(home_x, home_y, rock_x, rock_y) <= 1000:
        visited[n] = True
        return

    que = deque()

    for i in range(len(conveni)):
        temp = cal_distance(home_x, home_y, conveni[i][0], conveni[i][1])
        if temp <= 1000:
            que.append(conveni[i])
            visited[i] = True

    while que:
        cx, cy = que.popleft()
        for i in range(len(conveni)):
            temp = cal_distance(cx, cy, conveni[i][0], conveni[i][1])
            if temp <= 1000 and not visited[i]:
                que.append(conveni[i])
                visited[i] = True

t = int(input())

for _ in range(t):
    n = int(input())
    visited = [False] * (n + 1)
    conveni = []

    home_x, home_y = map(int, input().split())

    for _ in range(n):
        conveni.append([int(a) for a in input().split()])

    rock_x, rock_y = map(int, input().split())
    conveni.append([rock_x, rock_y])

    bfs()

    if visited[n] == True:
        print('happy')
    else:
        print('sad')

---

코드 설명

1. 메인

t = int(input())

for _ in range(t):
    n = int(input())
    visited = [False] * (n + 1)
    conveni = []

    home_x, home_y = map(int, input().split())

    for _ in range(n):
        conveni.append([int(a) for a in input().split()])

    rock_x, rock_y = map(int, input().split())
    conveni.append([rock_x, rock_y])

    bfs()

    if visited[n] == True:
        print('happy')
    else:
        print('sad')

입력받은 테스트 케이스 개수 t개만큼 반복한다.

입력받은 페스티벌 좌표는 편의점 리스트에 추가해 준다.

conveni[n]은 페스티벌의 인덱스가 된다.

따라서 그래프 탐색(bfs)을 하고 visited[n] = True이면 페스티벌에 갈 수 있다는 뜻이므로 

'happy'를 출력해 준다. False면 'sad'를 출력해 준다.

 

2. bfs

def bfs():
    if cal_distance(home_x, home_y, rock_x, rock_y) <= 1000:
        visited[n] = True
        return

    que = deque()

    for i in range(len(conveni)):
        temp = cal_distance(home_x, home_y, conveni[i][0], conveni[i][1])
        if temp <= 1000:
            que.append(conveni[i])
            visited[i] = True

    while que:
        cx, cy = que.popleft()
        for i in range(len(conveni)):
            temp = cal_distance(cx, cy, conveni[i][0], conveni[i][1])
            if temp <= 1000 and not visited[i]:
                que.append(conveni[i])
                visited[i] = True

먼저, 집에서 바로 페스티벌로 갈 수 있으면 탐색 없이 바로 리턴해준다.

 

탐색전에 집에서 갈 수 있는 편의점을 전부 큐에 추가해 준다.

 

입력받은 편의점 좌표들은 while문에서 하나씩 pop을 하며 그래프를 탐색해 나간다.

방문하면 visited = True로 변경해 준다.

 

 

3. calculate distance(맨해튼 거리)

def cal_distance(x, y, nx, ny):
    return abs(nx - x) + abs(ny - y)

간단히 거리 구하는 코드를 구현했다. x, y 거리차를 더해주면 된다.