백준 9205 맥주 마시면서 걸어가기 파이썬

백준 9205 맥주 마시면서 걸어가기 풀이

접근방식

1. 큐 자료구조를 이용한 너비우선탐색으로 해결합니다.
2. 출발위치, 편의점 위치, 페스티벌 위치를 따로 따로 입력받도록 합니다.
   (home) (conv) (fest)
3. 만약 집에서 페스티벌의 거리가 1000이하라면 편의점을 들르지 않아도 되므로 바로 “happy”를 출력해줍니다.
4. 편의점을 걸쳐서 갈 경우, 현재의 위치에서 편의점까지의 거리가 1000이하라면
   이동해도 되므로 q에 편의점 위치로 지정된 new_x, new_y를 x,y로 append 시켜줍니다.
5. 그렇다면 이후에는 현재 위치가 이전에 들른 편의점의 위치가 됩니다.
6. 위의 과정을 q가 빌때까지 수행해주고, 모두 완료되었다면 “sad”를 출력해줍니다.
7. “sad”를 출력하는 이유는 while문이 수행되었을 때, “happy”가 출력되지 않는다면
   도달할 수 없다는 의미이므로 while문 밖에 print(“sad”) 와 return을 넣어줍니다.

정답코드

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

# 테스트 케이스
t = int(input())

def bfs():
    q = deque()
    q.append([home[0], home[1]])
    while q:
        x,y = q.popleft()
        if abs(x-fest[0]) + abs(y-fest[1]) <= 1000:
            print("happy")
            return
        for i in range(n):
            if not visited[i]:
              # 새로운 좌표로 방문하지 않은 편의점 위치 지정
                new_x, new_y = conv[i]
                if abs(x-new_x) + abs(y-new_y) <= 1000:
                  # 현재 위치를 방금 거리를 비교한 편의점 위치로 지정
                    q.append([new_x, new_y])
                    visited[i] = True
    # 모두 만족하지 못했다면 sad 출력
    print("sad")
    return




for _ in range(t):
    n = int(input())
    home = [int(x) for x in input().split()]
    conv = []
    for j in range(n):
        x, y = map(int, input().split())
        conv.append([x, y])
    fest = [int(x) for x in input().split()]
    visited = [False for i in range(n+1)]
    bfs()

해당 문제는 실버 1레벨의 너비 우선 탐색 문제였습니다.

이 문제는 출발, 편의점, 목적지의 위치를 따로 입력받아 거리를 비교해주도록

하는 부분에서 어렵다고 느꼈고, 좌표 이동 문제는 자연스럽게 bfs로 접근해야 한다는 것을

배울 수 있었습니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady