본문 바로가기
반응형

알고리즘/너비 우선 탐색(bfs)24

백준 2146번 : 다리 만들기 java 이 문제는 bfs를 이용하여 한 섬에서 다른 섬까지의 최단 거리를 찾아서 다리를 만드는 문제입니다. 저는 이 문제를 풀기 위해서 우선 각각의 섬들을 나누었고 다른 섬에 접촉한다면 다리를 만들게 하였습니다. 이를 예제 1번을 예시로 간단히 보여드리겠습니다. 위의 그림과 같이 저는 우선 이 지도의 각각의 좌표들을 확인하여 연결된 부분들을 하나의 섬으로 묶은 다음 같은 섬에 속해있는 땅의 숫자를 같게 만들었습니다. 이후 각각의 섬에서 bfs를 실행하여 가장 먼저 자신의 섬과 다른 섬에 닿았을 때 다리를 건설하게 했습니다. import java.io.*; import java.util.*; public class Main { static int N, min = Integer.MAX_VALUE; static in.. 2022. 8. 8.
백준 5014번 : 스타트링크 java 이 문제는 너비 우선 탐색을 이용하여 S층에서 G층으로 가기까지 눌러야 하는 버튼의 수의 최솟값을 구하는 문제입니다. 이 문제를 풀기 위해서는 U와 -D 만큼 현재 위치한 층에서 이동하면서 이미 방문한 층이라면 방문하지 않고 방문하지 않았다면 그 층으로 가기 위해서 필요한 버튼의 클릭수를 저장하면서 이동하면 됩니다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new Stri.. 2022. 8. 5.
백준 19238번 : 스타트 택시 java 이 문제는 아기 상어 문제와 유사한 부류의 문제입니다. bfs를 이용하여 출발지에서 도착지까지 가는 거리를 구해서 가스의 양을 확인하면서 진행하는 문제입니다. 이 문제에서는 택시가 출발하여 가장 가까운 거리에 있는 사람을 태운 다음에 그 사람의 목적지까지 택시를 이동시켜주면됩니다. 문제에서 주어진 조건들을 하나하나 구현해주면 되는 문제입니다. import java.io.*; import java.util.*; public class Main { static int N, gas; static boolean canGo = true; static int[][] map; static Node[] start; static Node[] arrival; static int[] dR = {1, -1, 0, 0}; st.. 2022. 7. 28.
백준 2638번 : 치즈 java 이 문제는 (0, 0)에서 bfs를 실행하여 위의 그림 1, 2, 3과 같이 바깥공기와 2면 이상이 닿은 치즈들을 녹이면서 몇 초 후에 치즈가 전부 없어지는지 구하는 문제입니다. 저는 각각의 치즈가 주변에 공기가 몇 칸이 있는지를 확인하기 위해서 air 배열을 이용하였습니다. import java.io.*; import java.util.*; public class Main { static int N, M, cheeseNum = 0, time = 0; static int[][] map; static int[][] air; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; public static void main(String[] args.. 2022. 7. 26.
백준 24444번 : 알고리즘 수업 - 너비 우선 탐색 1 java 이 문제는 bfs를 이용하여 정점들을 탐색하면서 각 정점별로 호출된 순서를 출력하는 문제입니다. 이 문제의 예제를 통해 설명드리도록 하겠습니다. 이 문제의 예제를 그래프로 나타내면 다음과 같습니다. 시작 정점이 1번이니 여기서 시작하여 bfs를 순서대로 실행하는 모습을 보여드리겠습니다. bfs를 통해서 순서를 타고 내려갈 때 정점의 수가 적은 순으로 내려가니 그다음은 2번 노드와 4번 노드 중에서 2번 노드로 갑니다. 이제 2번 노드를 탐색했으니 1번 노드와 연결되어 있던 4번 노드를 탐색해줍니다. 이제 2번 노드와 연결되어 있던 3번 정점을 탐색해줍니다. 5번 정점을 갈 수 없으므로 0을 넣어줍니다. 다음과 같은 알고리즘으로 이 문제를 해결하실 수 있습니다. import java.io.*; import.. 2022. 7. 17.
백준 6118번 : 숨바꼭질 java 이 문제는 1번 정점에서 탐색을 시작하여 1번 정점에서 다른 정점에 이르기까지 얼마의 시간이 걸리는지 찾는 문제입니다. 위의 사진은 이 문제에서 힌트로 나와 있는 그림입니다. 이 그림과 같이 1번 정점을 기준으로 가장 멀리 떨어져 있는 정점들을 찾으면 됩니다. 이 그림에서는 4, 5, 6이 1에서 거리가 2로 가장 먼 정점들입니다. 그리고 거리가 같을 때는 정점의 번호가 가장 작은 정점에 숨으므로 숨어야 하는 정점은 4이고 거리는 2, 이 헛간과 같은 거리에 있는 헛간의 수는 3개입니다. import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static boolean[] .. 2022. 7. 12.
백준 1743번 : 음식물 피하기 java 이 문제는 각각의 칸들을 순회하면서 dfs 또는 bfs를 하여 음식물이 떨어진 구간의 크기가 가장 큰 구간의 크기를 출력하면 되는 문제입니다. import java.io.*; import java.util.*; public class Main { static int R, C, max = Integer.MIN_VALUE; static int[] dR = {1, -1, 0, 0}; static int[] dC = {0, 0, 1, -1}; static int[][] map; static boolean[][] visited; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new In.. 2022. 7. 10.
백준 2660번 : 회장뽑기 java 이 문제는 각각의 회원들을 bfs를 이용해서 조사하면서 다른 회원들과 몇 번의 연결을 통해서 전부 연결되는지 확인하는 문제입니다. 이 문제에서 모든 회원들이 자신의 친구 즉 한 번의 연결만으로 연결된다면 1점을 가지게 됩니다. 그리고 모든 회원들이 자신의 친구이거나 친구의 친구일 경우 2점을 가지게 되며 가장 점수가 낮은 사람이 회장이 된다고 합니다. 따라서 모든 회원들이 점수를 몇 점을 가지는지 검사해주고 점수가 가장 낮은 사람의 점수와 후보의 수, 그 후보의 번호를 출력하면 됩니다. import java.io.*; import java.util.*; public class Main { static int N; static List l = new ArrayList(); static int[] point.. 2022. 7. 9.
반응형

티스토리툴바