본문 바로가기

BFS

 (29)
[백준 / BOJ] 16953 A -> B 문제 출처 : www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 정수 A와 B가 주어진다. A에 *2연산과, A*10+1연산을 할수있을때, A를 B로 바꾸는데 필요한 최소연산횟수를 구하는 문제다. 이때, A를 B로 바꾸지 못한다면, -1을 출력하면 된다. 풀이 전형적인 BFS문제다. BFS알고리즘은 자기와 가까운 위치부터 탐색하기때문에, 항상 최소연산으로 A를 B로 바꿀수있다. A와 B의 범위가 최대 10억이기때문에, check배열로는 같은숫자방문을 체크해줄수없다. 하지만, 연산의 증가폭이 넓기때문에, 모든경우를 다 봐줘도 시간초과가 나지않는다. 예시로, 1. *2 연산은 32번만 반..
[백준 / BOJ] 13460 구슬 탈출 2 문제 출처 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 보드의 가로, 세로의 길이가 주어지고, 두 구슬 R,B의 위치가 주어진다. 보드를 기울여 구슬을 동서남북으로 움직일수있다. 단, 한번 움직이면, 벽, 다른 구슬, 구멍을 만날때까지 기울인 방향으로 움직여야한다. R구슬만 탈출시키는 최소한의 이동 횟수를 구하면 된다. 풀이 시키는대로 하면되는 구현문제다. BFS알고리즘을 이용해 풀었다. - check..
[백준 / BOJ] 12852 1로 만들기 2 문제 출처 : www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 숫자 N이 주어졌을때, 1. 나누기 2 2. 나누기 3 3. 빼기 1 을 적절히 사용하여 최소한의 연산으로 1을 만드는 문제다. 풀이 너비우선 탐색이기때문에, 항상 최소경로가 가장 먼저나오는 BFS를 사용해 최소 연산을 찾아주면된다. 경로는, 의 check배열에 {연산횟수, 이전 숫자}형태로 저장해준다. 이전숫자가 없을경우(처음숫자) 이전숫자 위치에 -1을 저장해놓는다. (연산횟수보다 작은 연산횟수가 나오지않는다면 check배열이 업데이트 되지않으므로 항상 성립한다) 배열을 따라 1부터 올라가며 경로를..
[백준 / BOJ] 17071 숨바꼭질 5 (1~5) 문제 출처 : www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이 문제는 다른 숨바꼭질 문제들과는 달리, 동생이 매 시간마다 +1 +2 +3 +4 +5 ... 의 속력으로 앞으로 질주한다. 이때, 수빈이가 동생을 찾는 가장 빠른 시간을 출력하는 문제다. 풀이 BFS로 풀리는 문제다. 우선 BFS로 수빈이가 해당 정점에 도달하는 최솟값들을 전부 갱신해주고 동생을 움직이며, 서로가 만날수있는지 봐줬다. (동생이 수빈이를 찾는..
[백준 / BOJ] 5427 불 문제 출처 : www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 상근이가 빌딩을 탈출하려고한다. 이때, 벽이있는곳이나 불이 붙은곳으로는 이동할수없다. 불은 1초마다 상하좌우로 번지며 벽으로는 번지지못한다. 상근이는 1초마다 상하좌우로 움직이며, 벽으로 이동하지 못한다. 가장빠르게 빌딩 밖으로 나가는 경우를 찾는 문제다. 풀이 BFS두번으로 풀리는 구현문제였다. 1. 우선, 불의 위치를 전부 저장해놓은다음, 각각의 위치를 기준으로 BFS를 돌린다. 이때 해당(y,x)지점에 ..
[백준 / BOJ] 20046 Road Reconstruction 문제 출처 : www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 � www.acmicpc.net m*n의 격자 모양의 격자가 있다. 격자의 각 칸에는 도로가 있을수도, 없을수도 있는데, 이 격자에 도로를 배치하여 (1,1)지점에서 (m,n)까지 가는 다리를 만들어야한다. 칸마다 도로를 만드는데 드는 비용은 다르다 (비용 1과 비용2가 있음) -1인 지점에는 도로를 만들지 못하고, 0은 이미 도로가 있는 곳이다. 비용을 최소한으로 사용..
[백준 / BOJ] 6146 신아를 만나러 문제 출처 : www.acmicpc.net/problem/6146 6146번: 신아를 만나러 키파는 신아를 만나러 아침 일찍(무려 6시에!) 일어났다. 간밤에 거센 비가 내려서 새로 산 장화를 신고 (0, 0)에 있는 집을 나선 키파는 무려 N(1 ≤ N ≤ 104)개의 웅덩이가 있는 것을 보고 놀랐다. www.acmicpc.net 키파는 신아에게 가야한다. 키파와 신아 사이에는 웅덩이가있고, 키파는 웅덩이를 피해서 가야한다.(키파가 신아에게 못가는경우는없다.) 키파의 위치는 항상 (0,0이고) 신아는 (-500~500, -500~500) 사이에 있다 키파는 상하좌우로만 움직일수있다. 풀이 BFS로 풀리는 문제였다. -500~500까지 가능하므로 전체 칸의 갯수는 1000 * 1000 = 1000000개..
[백준 / BOJ] 13931 숨바꼭질 4 문제 출처 : www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 수빈이와 동생은 숨바꼭질을 한다. 수빈는 자신의 위치에서 -1, +1, *2만큼 이동할수있다. 수빈이가 동생을 가장빨리 찾는 시간을 구하는 문제다. 풀이 BFS를 통해 푸는 문제였다. 배열을 이용해 자신의 전 위치를 체크해줘야하는데, 예를들어, 배열이 par[100005]로 선언되어있고 수빈이가 동생에게 가는 경로가 5 10 20 40 이라면, par[40]..

티스토리툴바