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

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

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

https://github.com/HPYoo/swcodingtest/blob/main/prob9205.py

GitHub - HPYoo/swcodingtest: 코딩테스트 대비 연습

실버 1 수준의 기본적인 BFS 문제

 

1. 어떻게 구성할 것인가?

 -1) 먼저, 집 위치를 큐에 먼저 넣고 반복문 실시

 -2) 큐에서 위치정보를 빼내고 축제장소에 바로 갈 수 있는지 확인, 가능하다면 종료

 -3) 불가능할 경우 편의점과 거리를 측정 1000미터 이하인 경우에만 새로 큐에 넣고 방문처리(재방문 안 해도 됨)

 -4) 2번과 3번 과정 반복, 큐가 다 빠진 경우라면 갈 수 없으므로 'sad'출력

 ※ 방문처리를 해두지 않으면 반복문 돌면서 처음부터 계속 확인하기 때문에 메모리 초과 문제가 발생한다.

그림으로 그려보면 다음과 같은 과정이다.

 

 

 

2. 전체 코드

 메모리 117356 KB, 시간 200 ms

참고 : deque 안 쓰고 리스트 append, del 써도 되긴 함.

from collections import deque
t = int(input())

def bfs(x, y, c_arr, f_arr):
    q = deque([[x, y]])
    while q :
        x, y = q.popleft()
        # 계산 하기 전에 n-1 번째 위치에서 축제장소 도달 가능한가?
        if abs(f_arr[0] - x) + abs(f_arr[1] - y) <= 1000:
            print('happy')
            return
        for i in range(len(c_arr)) :
            if not visited[i] :
                nx, ny = c_arr[i]
                dist = abs(nx - x) + abs(ny - y)
                if dist <= 1000 :
                    q.append([nx, ny])
                    visited[i] = True
    print('sad')
    return

for _ in range(t):
    n = int(input())
    x, y = map(int, input().split())
    cvs_list = [list(map(int, input().split())) for _ in range(n)]
    fest = list(map(int, input().split()))
    visited = [False for _ in range(n + 1)]
    bfs(x, y, cvs_list, fest)