본문 바로가기
728x90

백준 bfs

[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++]백준 17070번: 파이프 옮기기 1 문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제이해 첫째 줄에 N을 입력한다. 두번째 줄부터 N x N 크기의 집의 상태를 입력한다. 빈칸은 0이며 벽은 1로 입력한다. (1, 1), (1, 2)에 위치해 있는 파이프를 (N, N)까지 이동시키는 방법의 수를 구해 출력한다. 이 문제에서 주의해야 할 점은 현재 파이프의 방향에 따라 파이프를 옮길 수 있는 방법이 정해져있다는 것이다. 파이프가 가질 수 있는 모양.. 더보기
[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.. 더보기
LIST

티스토리툴바