[BOJ] 백준 9205 맥주 마시면서 걸어가기 / BFS

이미지를 클릭하면 문제 사이트로 이동합니다.

 

💭 문제 이해

맨해튼 거리로 계산해서 1000미터 이내에 편의점이 있다면 맥주를 20병으로 갱신할 수 있다.

 

편의점 좌표 또는 페스티벌 좌표가 들어있는 리스트를 탐색해서 1000미터 내에 있다면 queue에 넣고,

만일 그 좌표가 페스티벌 좌표라면 도착했다는 결과로 "happy"를 출력하고 종료한다.

 

BFS 연산을 위한 queue가 비어서 while 문이 종료되었다면,

가진 맥주 20병으로는 도달할 수 없다는 뜻으로 "sad"를 출력하게 된다.

 

 

구현 언어: Python

 

import sys
from collections import deque

r = sys.stdin.readline


def distance(n_x, n_y, x, y):
    return abs(n_x - x) + abs(n_y - y)


def solve(n, songdo):
    start_x, start_y = songdo[0]  # 시작점 좌표
    dest_x, dest_y = songdo[-1]  # 도착점 좌표
    store = songdo[1:]
    queue = deque()
    visited = []

    queue.append([start_x, start_y])  # 시작점부터 추가
    while queue:
        now_x, now_y = queue.popleft()

        for coor_list in store:
            if coor_list not in visited:
                if distance(now_x, now_y, coor_list[0], coor_list[1]) <= 1000:
                    # 그 지점이 도착점이라면 happy
                    if coor_list[0] == dest_x and coor_list[1] == dest_y:
                        return "happy"
                    visited.append(coor_list)  # 방문처리 list에 추가
                    queue.append(coor_list)
    return "sad"


t = int(r())  # 테스트 케이스의 개수
for _ in range(t):
    n = int(r())  # 편의점의 개수
    songdo = [list(map(int, r().split())) for _ in range(n + 2)]  # 좌표 입력
    print(solve(n, songdo))

 

* 나는 방문 처리를 리스트에 집어넣어서 매번 완전 탐색을 해야한다.

이 문제를 푸는 데에는 지장이 없지만, 데이터 수가 더 늘어나면 효율적이지 않을 수도 있다.

 

다른 풀이를 찾아보니, 좌표를 모아놓은 리스트의 인덱스를 딕셔너리에 저장해서 푼 것을 보았다.

그렇게 구현한다면 방문 여부를 체크할 때 걸리는 시간을 더 줄일 수 있다!