[백준 9205] 맥주 마시면서 걸어가기 - python (solved.ac - 실버 1)

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

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

풀이

문제를 보았을때 알수있는 힌트

문제를 보고 시작점과 도착점이 있어서 bfs관련해서 풀어야겠다는 생각이 들었다.

중간에 들렸다가 가야하는 것이 다른 조건을 가지고 있다.

bfs 돌면서 중간에 들리는 곳을 확인하여 갈수있는지 갈수있다면 방문하게끔 코드를 짜면 된다.

import sys
from collections import deque


input = sys.stdin.readline

t= int(input())

for _ in range(t):
    n = int(input())
    dp =[]
    for i in range(n+2):
        dp.append(list(map(int,input().split())))
    visited =[False]*(n+2)

    queue = deque([[dp[0][0],dp[0][1]]])
    visited[0]=True
    while queue:
        x,y=queue.popleft()
        for i in range(n+2):
            if visited[i]==False:
                if abs(x-dp[i][0])+abs(y-dp[i][1])<=1000:
                    queue.append([dp[i][0],dp[i][1]])
                    visited[i]=True

    # print(visited[-1])
    if visited[-1]:
        print("happy")
    else:
        print("sad")

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon9205.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리