본문 바로가기

BFS30

[탐색/BFS] 백준 21736 헌내기는 친구가 필요해 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 2. 문제 풀이 전형적인 BFS 문제입니다. 캠퍼스 내를 너비 우선 탐색해서 만날 수 있는 사람이 몇 명인지 찾아냅니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습.. 2023. 8. 4.
[탐색/BFS] 백준 24445 알고리즘 수업 - 너비 우선 탐색 2 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 2. 문제 풀이 BFS 탐색 알고리즘을 적용하는 예제 문제입니다. 2023.06.30 - [Algorithm] - [탐색/BFS] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - Python [탐색/BFS] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - Python [ Contents ] 1. 문제 (링크 참조) 24444번.. 2023. 6. 30.
[탐색/BFS] 백준 1325 효율적인 해킹 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) B 를 뜻하지만, 이 문제는 반대입니다. 이를 주의해서 BFS 알고리즘을 사용합니다. 3. 코드 from collections import deque import sys input = sys.stdin.readline # 입력 N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] for _ in range(M): A, B = map(int, input().split()) graph[B].append(A) # bfs ans = [] for i in range(1, N+1): visited = [False]*(N+1) queue = deque([i]) visited[i] = True cnt = 1.. 2023. 6. 30.
[탐색/BFS] 백준 11060 점프 점프 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 2. 문제 풀이 1칸부터 N칸까지 있으며 각 칸에 쓰인 숫자만큼 최대로 점프할 수 있습니다. 2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python [탐색/BFS] 백준 1697 숨바꼭질 - Python [ Contents ] 1. 문제 (링크 참조) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,00.. 2023. 6. 30.
[탐색/BFS] 백준 1926 그림 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 2. 문제 풀이 1로 이어진 그림의 개수와, 그림의 최대 크기를 구하는 BFS 문제입니다. 2022.02.23 - [Algorithm] - [탐색/BFS] 백준 1012 유기농 배추 - Python [탐색/BFS] 백준 1012 유기농 배추 - Python [ Contents ] 1. 문제 (링크 참조) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 .. 2023. 6. 30.
[탐색/BFS] 백준 5014 스타트링크 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 문제 풀이 1층부터 F층까지 있는 건물에서 엘리베이터를 타고 S층에서 G층으로 가는 문제입니다. 엘리베이터는 U층만큼 오르며, D층만큼 내려갑니다. G층으로 가기위해 필요한 최소 버튼 횟수를 구해야 합니다. (G층에 갈 수 없을 시, use the stairs를 출력합니다.) 2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python [탐색/BFS] 백준 1697 숨바꼭질 - .. 2023. 6. 30.
[탐색/BFS] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - Python [ Contents ] 1. 문제 (링크 참조) 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 2. 문제 풀이 너비 우선 탐색(BFS)을 사용하는 기본 예제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를.. 2023. 6. 30.
[탐색/BFS] 백준 2206 벽 부수고 이동하기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 문제 풀이 최단 경로를 찾는 문제로, 임의로 벽 1개를 부술 수 있습니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents .. 2022. 10. 24.
[탐색/BFS] 백준 13913 숨바꼭질 4 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 문제 풀이 수빈이는 1초에 +1, -1, *2만큼 이동할 수 있습니다. X 지점에서 Y로 이동하는 최소 시간을 구해야 합니다. 2022.02.24 - [Algorithm] - [탐색/BFS] 백준 1697 숨바꼭질 - Python [탐색/BFS] 백준 1697 숨바꼭질 - Python [ Contents ] 1. 문제 (링크 참조) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질.. 2022. 8. 12.

티스토리툴바