본문 바로가기
728x90

백준 너비우선탐색

[C++]백준 5014번: 스타트링크 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제이해 첫째 줄에 F, S, G, U, D를 입력한다. 강호가 S층에서 G층으로 가기 위해서 눌러야 하는 버튼 수의 최솟값을 출력한다. G층으로 갈 수 없다면 "use the stairs"를 출력한다. S층에서 G층으로 가는 최단 거리를 찾는 문제로 너비 우선 탐색(BFS)를 이용하여 풀어야 되는 문제이다. 큐(queue)에 강호가 처음에 있는 층인 S층을 넣고 시작한다. 이후 큐(queue)의 fro.. 더보기
[C++]백준 7576번: 토마토 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제이해 N과 M을 입력한다. 각 칸에 대한 정보를 담은 N x M 크기의 상자를 입력한다. 모든 토마토가 익을 때까지의 최소 날짜를 출력한다. 다만 모든 토마토가 익지 못하는 상황의 경우 -1을 출력한다. 모든 토마토가 익을 때까지의 최소 날짜를 구하기 위해서는 너비우선탐색(BFS)을 이용하여 문제를 해결해야 한다. 큐(queue)에 현재 익은 토마토들의 정보를 넣고 pop.. 더보기
[C++]백준 1697번: 숨바꼭질 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제이해 수빈이의 위치와 동생의 위치를 입력한다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾기 위해 사용할 수 있는 방법은 다음과 같다. 수빈이의 기존위치 + 1로 이동하고 1초가 지난다. 수빈이의 기존위치 - 1 로 이동하고 1초가 지난다. 수빈이의 기존위치 * 2 로 이동하고 1초가 지난다 수빈이가 이동했던 자리는 다시 갈 필.. 더보기
LIST

티스토리툴바