본문 바로가기

Algorithm/BFS

 (63)
(C++) - 백준(BOJ) 2665번 : 미로만들기 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net bfs로 해결한 문제였습니다. 풀이방법 1. 최소로 벽을 부수는게 0일 수 있으므로 정답을 확인할 배열 ck를 -1로 초기화해줍니다. 2. 입력을 받은 후 bfs를 시행합니다. 2-1. 시작점 0,0을 queue에 push한 후 ck를 0으로 갱신해줍니다. 2-2. q가 빌 때까지 수행하는데 주의할 것은 최단거리로 이동했을 때 바꿔준 방의 개수가 최소임을 보장할 수 없는 점입니다. 갱신해줘야하는 시점을 ..
(C++) - 백준(BOJ) 19238번 : 스타트 택시 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현 + bfs 문제였습니다. 풀이방법 1. 입력 받은 후 손님의 데이터를 구조체를 이용해 벡터 형태로 저장합니다. 구조체는 손님의 출발 행,열 그리고 도착 행,열 그리고 택시까지의 거리로 이루어져 있습니다. 2. 택시의 위치에서 각 지점의 거리를 계산해줍니다. 계산된 배열 dist를 확인하며 손님과 택시사이의 거리를 모두 갱신해줍니다. 최단 거리의 손님을 ..
(C++) - 백준(BOJ) 15591번 : MooTube(Silver) https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net bfs문제였습니다. 풀이방법 모든 정점을 bfs를 통해 확인하며 현재 정점에서 다음정점으로 가는데 USADO 즉, cost가 기존에 저장된 다음정점의 cost보다 작다면 dist배열을 최솟값으로 갱신해주면 됩니다. 그 후 모든 dist를 확인하며 k값 이상인 개수를 세준 후 반환한 뒤 출력합니다. Code #include #define ll lo..
(C++) - 백준(BOJ) 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 bfs로 푼 문제였습니다. 비슷한 문제로는 숨바꼭질 문제가 있습니다. 풀이방법 입력받은 후 bfs를 수행합니다. 올라갈 수 있다면 queue에 다음 층을 방문하고 누른 버튼 수를 함께 queue에 pair형태로 push해줍니다. 내려갈 수 있다면 마찬가지고 push해줍니다. *pop이후에 방문하게 된다면 한 줄만에 방문해서 더 깔끔해 보이지만 시간초과가 납니다. x+u와 x-d가 다음 경로에서 엇갈리면서 중복..
(C++) - 백준(BOJ) 17142번 : 연구소 3 www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 여러가지 알고리즘을 사용하는 문제였습니다. 풀이방법 1. 입력을 받습니다. vector pair 형태로 2인 부분의 행,열 좌표를 virusPos 변수에 저장해줍니다. 그 외 필요한 변수들을 선언해줍니다. 2. 바이러스를 m개 놓아야합니다. backtracking을 이용해 조합으로 뽑아줍니다. 그 좌표들을 spreadPos변수에 저장합니다. 3. bfs를 수행합니다. 그 후 가장 큰 값이 마지막으로 퍼졌을 때의 시간입니..
(C++) - 백준(BOJ) 11967 번 : 불켜기 www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net bfs를 이용한 구현 문제였습니다. 풀이방법 bfs 유의사항 : 스위치를 켜버리고 그곳을 방문처리할 경우 이런 경우를 처리할 수 가 없습니다. 처음에는 바로 옆방이 불이 안켜져있어 들어가지 못했지만 나중에 다른 방에서 옆방의 불을 켤 경우에는 돌아와서 그곳으로 방문을 해야합니다. 따라서 한 번만 방을 방문하는 것이 아니고 경우에 따라 방문여부를 결정해야 합니..
(C++) - 백준(BOJ) 2636번 : 치즈 www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net bfs문제였습니다. 풀이방법 1. 판의 테두리는 0이 보장되므로 0,0지점은 0이라고 할 수 있습니다. 2. 입력을 받고, 모두 녹을 때까지 loop를 돕니다. 2-1. 먼저 치즈칸의 개수를 cnt변수에 저장합니다. 2-2. 외부공기임을 표시하기 위해 checkAir함수를 시행합니다. 이는 0,0부터 시작해 bfs를 시행해 모든 외부공기 칸을 -1로 만들어줍니다. 2-3. bfs를 시행합니다. 이는 외부공기와 맏닿아있는..
(C++) - 백준(BOJ) 13913번 : 숨바꼭질 4 www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs문제였습니다. 풀이방법 숨바꼭질 1과 푸는 방식이 동일하나 출력해야하기 때문에 다음위치로부터 이전위치를 추측할 수 있도록 만들어줍니다. Code #include #define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; using pii = pair; int ck[100001],..

티스토리툴바