[BOJ 백준] 9205번 : 맥주 마시면서 걸어가기 - 파이썬, Python

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

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

 

전형적인 BFS 탐색을 활용해서 푸는 문제였다. 

 

상근이는 무조건 집 -> 편의점 -> 편의점 .. -> 페스티벌 로 움직이기 때문에 다음번 편의점에 가서 항상 맥주를 최대로 살 수 있다. 

 

굳이, 이동할 때 마다 이동거리를 50m로 나누면서 이동 가능 여부를 판단하지 않고

맥주를 20개 먹었을 때 갈 수 있는 최대 거리인 1,000m를 기준으로 다음번 편의점 또는 페스티벌 장 까지의 거리가 1,000m가 넘으면 가지 못한다는 것만 판단해주면 된다.

 

 

 

소스코드

import sys, math
from collections import deque
sys.stdin = open("input.txt", "r")

def bfs(x, y):
    global store, festival_x, festival_y
    queue = deque()
    queue.append((x,y)) 
    visited = []
    while queue:
        x = queue[0][0]
        y = queue[0][1]
        visited.append((x,y))
        if x == festival_x and y == festival_y: # 목적지에 도착
            print("happy")
            return
        queue.popleft()
        # 현재 위치에서 갈 수 있는 편의점을 큐에 넣는다.
        for pos in store:
            dist = abs(x - pos[0]) + abs(y - pos[1]) # 맨하튼 거리
            if 1000 >= dist and pos not in visited: # 맥주를 먹으며 갈 수 있는 거리라면 큐에 넣는다
                queue.append((pos[0], pos[1]))
                visited.append((pos[0], pos[1]))
    print("sad")


for _ in range(int(input())):
    n = int(input()) # 편의점의 개수
    sang_x, sang_y = map(int,input().split()) # 상근이의 집 좌표 (출발)
    store = []
    for _ in range(n):
        store_x, store_y = map(int, input().split()) # 편의점 좌표
        store.append((store_x, store_y)) 
    festival_x, festival_y = map(int, input().split()) # 락 페스티벌 좌표 (도착)
    store.append((festival_x, festival_y))  # 락 페스티벌에 도착했는지 확인하기 위해 리스트에 삽입
    bfs(sang_x, sang_y)
    
    

 

 

좀 더 파이써닉한 코드 

• 편의점 좌표 값을 c++ 에서 하듯이 for loop을 돌지 않고 한번에 받는다.
• 위의 코드는 좌표를 tuple 타입으로 넣었는데 밑의 코드에서는 list 타입으로 넣었다.
  • 이 문제는 좌표가 바뀔일이 없기 때문에 tuple이든, list든 큰 문제는 없다. 
• 주의할 점은 리스트의 원소가 tuple, list형 이 섞여서 들어가면 안된다. (2, 3) 과 [2, 3]은 아예 다르게 인식한다.

import sys, math
from collections import deque
sys.stdin = open("input.txt", "r")

def bfs(x, y):    
    queue = deque()
    queue.append([x,y]) 
    visited = []
    while queue:
        x, y = queue.popleft()               
        visited.append([x,y])
        if x == festival_x and y == festival_y: # 목적지에 도착
            print("happy")
            return
        # 현재 위치에서 갈 수 있는 편의점을 큐에 넣는다.
        for nx, ny in store:
            dist = abs(x - nx) + abs(y - ny) # 맨하튼 거리
            if 1000 >= dist and [nx, ny] not in visited: # 맥주를 먹으며 갈 수 있는 거리라면 큐에 넣는다
                queue.append([nx, ny])
                visited.append([nx, ny])
    print("sad")


for _ in range(int(input())):
    n = int(input()) # 편의점의 개수
    sang_x, sang_y = map(int,input().split()) # 상근이의 집 좌표 (출발)
    # store = []
    # for _ in range(n):
    #     store_x, store_y = map(int, input().split()) # 편의점 좌표
    #     store.append([store_x, store_y]) 
    
    store = [list(map(int, input().split())) for _ in range(n)] # 조금 더 파이써닉 하게 짰음
    
    festival_x, festival_y = map(int, input().split()) # 락 페스티벌 좌표 (도착)
    store.append([festival_x, festival_y])  # 락 페스티벌에 도착했는지 확인하기 위해 리스트에 삽입
    bfs(sang_x, sang_y)