[Python] 백준 9205 맥주 마시면서 걸어가기

 

문제 분석

• 맥주 1박스 20개
• 50m에 한 병씩
• 가면서 편의점에서 맥주를 더 구매해야 할 수도 있다.
• 편의점에 들렸을 때, 빈 명은 버리고, 새 맥주 병을 살 수 있는데 박스에 들어있는 맥주는 20병을 넘을 수 없다.
• 편의점을 나선 직후에서도 50m를 가기 전 맥주 한 병을 마셔야 한다.
  • 편의점을 도착하면 이전에 얼마를 마시든 리셋

 

풀이

• 시작 좌표, n개의 편의점 좌표, 도착 좌표
• 20병, 1병당 50m → 한 번에 1,000m 갈 수 있다.
  
  
• 편의점에 도착하면 20병 리셋 : 고려할 필요 없을 듯
  
  
• bfs 너비 우선 탐색
• 최적의 경로를 찾아가면서 현재 위치부터 다음 위치까지의 거리를 계산하고
• 그 중 거리가 1000 초과가 있으면 bad
• 거리가 모두 1000 이하이면 happy

 

정답 코드

실패

import sys
from collections import deque
input = sys.stdin.readline

testcase = int(input())

def distance(x1, y1, spot2) :
    x2, y2 = spot2
    return abs((x1-x2) + (y1-y2))

for tc in range(testcase) :
    con_n = int(input()) # 편의점 수
    visited = [0] * con_n

    start = list(map(int, input().split()))
    # 최적의 거리에 대한 정렬 필요
    con_list = [list(map(int, input().split())) for _ in range(con_n)]
    end = list(map(int, input().split()))

    def bfs() :
        q = deque(start)

        while q :
            x, y = q.popleft()
            # x,y = current

            for i in range(len(con_list)) :
                if visited[i] == 0 :
                    if (x, y, con_list[i]) :
                        q.append(con_list[i])
                        visited[i] = 1
                    else :
                        return 'sad'

            if len(q) == 0 : # 큐가 비어서 while 문을 빠져나가기 전에 도착위치와 비교
                if (x, y, end) :
                    return 'happy'
                else :
                    return 'sad'

    print(bfs())

 

다른 정답 코드 1

import sys
from collections import deque

input = sys.stdin.readline

def bfs() :
    q = deque()
    q.append((home_x, home_y))

    while q :
        x, y = q.popleft()
        if abs(x-fest_x) + abs(y-fest_y) <= 1000 :
            print('happy')
            return

        for i in range(n) : # 편의점들 확인
            if not visited[i] :
                nx, ny = g[i]

                if abs(x-nx) + abs(y-ny) <= 1000 : # 다음 거리까지 갈 수 있다면
                    visited[i] = 1
                    q.append((nx, ny))
    print('sad')
    return 

testcase = int(input())
for tc in range(testcase) :
    n = int(input())
    home_x, home_y = map(int, input().split())
    g = [list(map(int, input().split())) for _ in range(n)]
    fest_x, fest_y = map(int, input().split())

    visited = [0 for _ in range(n)]
    bfs()

 

 

2회차 - 25.03.20

import sys
input = sys.stdin.readline
from collections import deque

def bfs() :
    d = deque()
    d.append((home_x, home_y))
    v = [False for _ in range(n)] # 편의점 방문 확인

    while d :
        x, y = d.popleft()

        if (abs(x - fest_x) + abs(y - fest_y)) <= 1000:
            print('happy')
            return

        for i in range(n) :
            nx, ny = store[i]

            if not v[i] :
                # if (abs(x-fest_x) + abs(y-fest_y)) <= 1000 :
                #     print('happy')
                #     return

                if (abs(x-nx) + abs(y-ny)) <= 1000 :
                    d.append((nx, ny))
                    v[i] = True

    print('sad')
    return

tc = int(input())
for _ in range(tc) :
    n = int(input()) # 편의점 수

    home_x, home_y = map(int, input().split())
    store = [list(map(int, input().split())) for _ in range(n)]
    fest_x, fest_y = map(int, input().split())

    bfs()