[백준/BOJ] - 9205번 python 풀이 - bfs

---

문제를 잘 파악하자

 

1. 현재 좌표 기준으로 페스티벌에 갈 수 있는지 항상 확인한다.

 

-  갈 수 있으면 "happy"를 출력하고 bfs 함수 return

 

2. 불가능할 경우

 

- 편의점 좌표를 입력할 때 저장시킨 리스트를 가지고 반복문을 돌린다.

- 해당 idx의 편의점 방문 기록이 없을 경우 해당 편의점 좌표를 뽑아내어 현재 좌표에서 해당 편의점으로 바로 갈 수 있는지 여부를 확인한다.

- 가능하다면 queue에 해당 좌표를 저장시키며 방문처리를 진행한다. (방문처리는 편의점 좌표만을 위한 것이다.)

- 이런식으로 하다가 페스티벌 좌표로 접근 가능 할 경우 "happy" 출력하고 종료

- happy 출력 부분에서 return하지 못했을 경우 커서가 while문 바깥에 도달하게 될 것이므로 해당 위치에 "bad" 출력하는 코드를 작성한다.

 

---

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


def bfs():
    q = deque()
    q.append((x1,y1)) #집 좌표
    while q:
        r1,r2 = q.popleft() #집, 편의점..
        if abs(p1-r1) + abs(p2-r2) <= 1000:
            print("happy")
            return

        for i in range(n): #편의점 개수
            if not ok[i]:
                c1, c2 = cs[i] #새로운 편의점 뽑아내기
                if abs(r1-c1) + abs(r2-c2) <= 1000:
                    q.append((c1, c2))
                    ok[i] = True
    print("sad")
    return

T = int(input())
for _ in range(T):
    n = int(input()) #편의점 수
    x1,y1 = map(int,input().split()) #집 좌표
    cs = []
    for _ in range(n): #편의점 입력받기
        x2,y2 = map(int,input().split())
        cs.append((x2,y2)) #편의점 리스트
    p1,p2 = map(int,input().split())
    ok = [False for _ in range(n+1)] #편의점 리스트 전용 방문 정보
    bfs()