BFS19 [Problem Solving] BOJ 11559: Puyo Puyo 문제 출처: https://www.acmicpc.net/problem/11559 4개 이상 연결되어 있는 뿌요들을 터뜨리면 다른 뿌요들이 중력에 의해 밑으로 떨어진다. 그 때 또 4개 이상 연결되어 있는 뿌요들이 터진다. 이런 식으로 연쇄 폭발이 일어나는 횟수를 구하는 문제이다. 다음과 같은 동작을 반복 수행한다.1. scan함수를 사용하여 4개 이상 연결되어있는 뿌요 그룹에 속한 어느 뿌요 하나의 위치들을 to_pop벡터에 담아서 받는다. (BFS를 사용해서 4개 이상 연결되어 있는 뿌요 그룹인지 찾는다.)2. 1에서 벡터가 비어있으면 break한다.3. pop_puyo 함수를 사용해서 to_pop에 있는 뿌요 그룹의 하나의 위치로 시작하여 BFS로 그 그룹을 필드에서 없앤다.4. drop 함수를 사용.. 2025. 5. 16. [Problem Solving] BOJ 17142: 연구소 3 문제 출처: https://www.acmicpc.net/problem/17142 N*N 격자가 있다.0: 통로1: 벽2: 바이러스이다. 바이러스 중에서 활성화된 바이러스를 M개 골랐을 때, 벽이 아닌 공간에 모두 퍼지는 시간의 최솟값을 구하는 문제이다.모든 조합에 대해서 다음을 수행한다.1. 조합을 고른다.2. N*N distance의 모든 원소를 무한대로 설정한다.3. 조합에서 각각의 바이러스 지점에서 bfs를 수행한다. (바이러스는 벽이 아닌 모든 곳으로 퍼질 수 있다.)4. 격자에서 모든 통로, 그리고 활성화된 바이러스 지점에 바이러스가 퍼질 때 까지 걸리는 최소 시간 중 최댓값을 구한다.5. 4에서 구한값과 이전 조합에서 구한 값을 비교해서 벽이 아닌 공간에 모두 퍼지는 시간의 최솟값을 갱신한다.. 2025. 5. 12. [Problem Solving] BOJ 1743: 음식물 피하기 문제 링크: https://www.acmicpc.net/problem/1743 인접한 쓰레기를 하나로 묶었을 때, 가장 큰 쓰레기 더미의 크기를 출력하는 프로그램이다.BFS를 수행해서 쓰레기 더미의 크기를 구해서 가장 큰 것을 출력하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static class Point { public int y; public int x; public Point(int y, int x) { this.y.. 2025. 3. 21. [Problem Solving] BOJ 5427 : 불 문제 링크 : https://www.acmicpc.net/problem/5427 건물에서 탈출해야 하는 데, 불이 탈출구까지 번지기 전에 탈출할 수 있는지, 그렇다면 최소 몇 초만에 탈출할 수 있는지 구하는 문제이다. 1. 사람에 대한 BFS를 수행하여, 사람이 처음 존재하는 격자에서 다른 격자까지 가는데 걸리는 최소 시간을 각 격자마다 구한다. 사람은 불이 최초로 난 곳과 벽을 제외한 모든 곳으로 움직일 수 있다.2. 불에 대한 BFS를 수행하여, 불이 있는 곳으로 부터 각 격자마다 번지게 되는 최소 시간을 계산한다. 불은 벽을 제외한 모든 곳에 번질 수 있다.3. 건물의 탈출구까지 불이 번지기 전에 지훈이가 도달할 수 있는 경우, 도달할 수 있는 시간 중 최소 시간을 구해서 출력한다. 그렇지 못한다면.. 2025. 2. 26. [Problem Solving] BOJ 4179 : 불! 문제 링크 : https://www.acmicpc.net/problem/4179 지훈이가 미로에서 탈출해야 하는 데, 불이 벽이 아닌 모든 곳으로 번지기 전에 탈출할 수 있는지, 그렇다면 몇분이 걸리는지 구하는 문제이다. 1. 불에 대한 BFS를 수행하여, 불이 있는 곳으로 부터 각 격자마다 번지게 되는 최소 시간을 계산한다. 불은 벽을 제외한 모든 곳에 번질 수 있다.2. 지훈이에 대한 BFS를 수행하여, 지훈이가 처음 존재하는 격자에서 다른 격자까지 가는데 걸리는 최소 시간을 각 격자마다 구한다. 지훈이는 불이 최초로 난 곳과 벽을 제외한 모든 곳으로 움직일 수 있다.3. 미로의 가장자리까지 불이 번지기 전에 지훈이가 도달할 수 있는 경우, 도달할 수 있는 시간 중 최소 시간을 구해서 출력한다. im.. 2025. 1. 29. [Problem Solving] BOJ 2146 : 다리 만들기 문제 링크 : https://www.acmicpc.net/problem/2146 섬들이 격자 안에 주어지고, 섬과 섬 사이의 최단거리 중, 가장 짧은 값을 출력하는 문제이다. 우선 섬마다 번호를 붙여야한다.격자를 순회하면서 섬이면서 방문하지 않은 노드라면 그 노드를 시작점으로 하여 BFS를 수행하여 그 노드가 속하는 섬에 cnt라는 번호를 붙여준다. 이제 섬과 섬 사이의 최단 거리 중 가장 짧은 값을 구해야한다.격자를 순회하면서 섬에 포함되는 격자에서 BFS를 수행한다.인접한 격자가 유효 범위에 있고, 아직 방문하지 않았는데, 바다라면, 큐에 추가하고, dist를 현재 위치의 dist + 1로 설정한다.인접한 격자가 유효 범위에 있고, 아직 방문하지 않았는데, 출발한 섬이 아닌 다른 섬에 포함되는 격자라.. 2025. 1. 12. 이전 1 2 3 4 다음