알고리즘/너비 우선 탐색(bfs)

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

2023. 2. 7. 23:04
목차
  1. 1. 문제 출처
  2. 2. 풀이
  3. 그래프 탐색 + BFS(너비 우선 탐색)

1. 문제 출처

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

 

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

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.

www.acmicpc.net

2. 풀이

# 테스트 테이스의 개수
t = int(input())
# 편의점 좌표 입력받는 함수
get_coordinate = (lambda : list(map(int,input().split())) )
# 길이 구하는 함수
get_legth = (lambda start , end : abs(start[0]-end[0])+abs(start[1]-end[1]))
# 결과 저장하는 리스트
result_list = []


for _ in range(t):
    # 편의점의 개수
    n = int(input())
    
    # 사용할 변수 초가화
    start = get_coordinate()
    queue = [start]
    con_list = []
    result = "sad"
    
    # 편의점 좌표 받기
    for _ in range(n):
        con_list.append(get_coordinate())
    # 페스티벌 좌표 받기
    end = get_coordinate()
    
    # 방문 여부
    visted = [-1 for i in range(n)]
    
    # queue가 빌동안 반복
    while queue:
        start = queue.pop(0)
        length = get_legth(start ,end)
        # 길이가 맥주 다 마시기 전까지 된다면 happy 로 하고 while문 종료
        if length <= 1000:
            result = "happy"
            break
        
        # 편의점 개수 만큼 반복
        for idx in range(n):
            # 만약 방문하지 않음 편의점일 경우
            if visted[idx] == -1:
                length = get_legth(start ,con_list[idx])
                # 현재 좌표에서 방문이 가능한지 구한다.
                if length <= 1000:
                    visted[idx] = 1
                    queue.append(con_list[idx])
    # 결과 리스트에 나온 결과를 추가한다.
    result_list.append(result)

# 결과 출력
for result in result_list:
    print(result)

그래프 탐색 + BFS(너비 우선 탐색)

'알고리즘 > 너비 우선 탐색(bfs)' 카테고리의 다른 글

16234-백준-인구이동  (0) 2023.02.23
18405-백준-경쟁적 전염  (0) 2023.02.18
18352-백준-특정 거리의 도시 찾기  (0) 2023.02.17
14502 - 백준 - 연구소  (0) 2023.02.15
7562-백준-나이트의 이동  (0) 2023.02.06
  • 1. 문제 출처
  • 2. 풀이
  • 그래프 탐색 + BFS(너비 우선 탐색)
'알고리즘/너비 우선 탐색(bfs)' 카테고리의 다른 글
  • 18405-백준-경쟁적 전염
  • 18352-백준-특정 거리의 도시 찾기
  • 14502 - 백준 - 연구소
  • 7562-백준-나이트의 이동
easysheep
easysheep
easysheep
나의 개발자 일기
easysheep
전체
오늘
어제
  • 분류 전체보기 (95)
    • 파이썬 (7)
      • 자료형 (0)
      • matplotlib (2)
      • Tensorflow (1)
      • Selenium (1)
      • Numpy (2)
      • Pandas (1)
    • 장난감 프로젝트 (3)
    • AI_수학 (0)
      • 통계 (0)
    • 알고리즘 (63)
      • 브루트 포스 (3)
      • 그리드 알고리즘 (5)
      • 너비 우선 탐색(bfs) (12)
      • 깊이 우선 탐색(DFS) (1)
      • 최단 경로 구하기(플로이드 워셜) (1)
      • 동적 계획법(Dynamic Programming) (8)
      • Dijkstra algorithm(데이크스트라 알.. (6)
    • Backend (1)
      • Django (1)
    • 딥러닝 (1)
      • Regression(회귀) (0)
    • 머신러닝 (3)
      • Daycon (1)
      • 직접 구현 (1)
    • AWS (3)
    • DB (2)
      • MongoDB (2)
    • kubernetes (3)
    • Docker (4)
    • Stress Test Toll (0)
      • Jmeter (0)
      • nGrinder (0)
    • Ubuntu (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 너비 우선 탐색
  • Cannot stat file /proc/528/fd/0: Permission denied
  • Bind Mounts
  • 파이썬
  • gradio
  • mysql
  • error
  • 데이크스트라
  • 알고리즘
  • Mac
  • ubuntu
  • 헬름 설치
  • grafana
  • error: version in "./docker-compose.yaml" is unsupported.
  • 머신 러닝
  • Python
  • aws
  • 문자열
  • helm
  • validate service connection
  • BFS
  • matplotlib
  • Docker
  • heap
  • dynamic programming
  • ML
  • 2*n 타일링
  • 백준
  • 우분투에 헬름 설치
  • Numpy

최근 댓글

최근 글

hELLO · Designed By 정상우.
easysheep
9205-백준-맥주 마시면서 걸어가기
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.