9205

날짜 : 2023. 05. 16

사용 언어 : python

 

문제

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

 

 

코드

import sys
from collections import deque

def bfs(r, c):
    q = deque()
    q.append([r, c])
    while q:
        x, y = q.popleft()  # 기준점
        #print(x, y, fest)
        dist = abs(fest[0] - x) + abs(fest[1] - y)  # 현재 위치~축제 거리
        if dist <= 1000:
            return True
        for i in range(n):
            if conv[i] not in visited:  # 편의점 방문 안한 경우
                if abs(conv[i][0] - x) + abs(conv[i][1] - y) <= 1000:  # 거리가 된다면
                    visited.append(conv[i])  # 추가
                    q.append(conv[i])  # 큐에 추가
    return False


t = int(sys.stdin.readline())  # 테스트케이스
for _ in range(t):
    n = int(sys.stdin.readline())  # 편의점 개수
    home = list(map(int, sys.stdin.readline().split()))  # 출발지
    conv = list()
    for _ in range(n):
        conv.append(list(map(int, sys.stdin.readline().split())))  # 편의점
    visited = []  # 편의점 방문체크
    fest = list(map(int, sys.stdin.readline().split()))  # 축제
    if bfs(home[0], home[1]):
        print("happy")
    else:
        print("sad")

 

 

풀이

- 조건에 맞게 출발지, 편의점, 종착지를 입력받는다.

- 그 다음 bfs를 활용해서 맨 처음지점을 큐에 넣은 다음, popleft 후에 기준좌표로 삼으면서 종착지와 의 거리를 비교한다.

- 백주 1병당 50미터를 이동 가능하기 때문에 맨해탄 거리는 1000 이하인 경우 도달 가능하다.

- 축제 지역까지의 거리가 1000이 넘은 경우 편의점을 거쳐 가야 하기 때문에 for문을 사용해 기준점~편의점간 거리를 측정 후 1000이 되지 않는다면 큐에 넣고 방문처리한다.(visited 리스트에 삽입)

- 이후 while문 안에서 축제 위치에 도달 가능하다면 True를, 불가능하다면(큐가 비어버린다면) False를 리턴하고, 그 값에 따라 아웃풋을 출력한다.

 

 

알게된 점

- 각 위치에서 모든 편의점 + 축제지역까지의 거리를 비교 후 탐색하는 것으로 생각해서 계속 헛다리만 짚었다.

- 분면 BFS인데 완전탐색으로 생각하는 바람에 문제를 확실하게 풀지 못한 것 같다.

- 수업 들으면서 문제를 풀려니 제대로 집중이 안되는건 확실한 것 같다;;

 

 

참고 사이트

-