본문 바로가기
728x90

너비우선탐색

[C++]백준 2468번: 안전 영역 문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제이해 첫째 줄에 N을 입력한다. 두번째 줄부터 NxN 크기의 영역의 정보를 입력한다. 안전한 영역의 최대 개수를 출력한다. 구현하는게 생각보다 간단한 문제입니다. 높이를 정하고 높이에 따라 잠기지 않는 영역을 발견하면 그 옆에 붙어있는 잠기지 않는 영역까지 구하기 위해 너비우선탐색(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++]백준 2178번: 미로 탐색 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제이해 첫째 줄에 N과 M을 입력합니다. 다음 줄부터 N x M 크기의 미로를 입력합니다. 단 각각의 수들은 붙어서 입력됩니다. 미로의 (1, 1)에서 (N, M)까지의 최단 경로를 출력합니다. 우선 각각의 수들이 붙어서 입력되기 때문에 문자열로 받아 한글자씩 분리하여 2차원 벡터에 넣으면 됩니다. 미로의 (1, 1)에서 (N, M)으로 가는 최단경로를 찾는 문제이기 때문에 너비우선탐색(BFS)를 사용하면 쉽게 해결할 수.. 더보기
[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

티스토리툴바