너비 우선 탐색31 [백준] 22352: 항체 인식 - JAVA https://www.acmicpc.net/problem/22352 풀이숫자로 채워진 N x M 크기의 격자가 2개 주어진다. 첫 번째 격자를 before, 두 번째 격자를 after라는 이름으로 이차원 배열에 저장했다. 문제의 내용은 before의 어떤 한 점에 백신을 놓는다면, 인접한 영역 중 같은 숫자의 영역들이 함께 동일한 값으로 업테이트 된다는 것이다. 업데이트 하였을 때 입력에서 주어진 after와 같으면 YES, 다르면 NO를 출력하면 된다. (0, 0) 부터 순회하면서 before와 after가 처음으로 달라지는 부분을 찾았다. 해당부분부터 bfs탐색을 통해 인접한 같은 값의 영역들을 after에 해당하는 값으로 바꿔주었다. 그 후, 다시 (0, 0) 부터 before와 after를 비교하.. 2024. 8. 19. [백준] 25195: Yes or yes - JAVA https://www.acmicpc.net/problem/25195 풀이방향그래프가 주어지고, 1번 정점에서 출발해 리프노드까지 도달해야한다. 이때, 팬클럽이 위치하는 정점들을 피해 리프노드까지 도달할 수 있는지 확인하는 문제이다. dfs탐색의 인자로 팬클럽을 만났는지 여부를 담아 진행했다. 리프노드에 갔을 때 팬클럽을 만난적이 없다면 boolean값을 갱신해준다. 방문처리를 하지 않고 진행했는데 그 이유는 주어진 그래프가 사이클이 없음이 보장되었고, 방문처리를 할 경우 1 -> 2 -> 4 의 루트로 여행했다면, 1 -> 3 -> 4 의 루트로 여행하는 것은 이미 4번 정점이 방문처리 되었기 때문에 진행이 안되는 문제가 있었기 때문이다. 따라서, 방문처리 없이 바로 이전 정점으로만 갈 수 없게 했다. .. 2024. 7. 13. [백준] 14217: 그래프 탐색 - JAVA https://www.acmicpc.net/problem/14217 풀이도시마다 연결된 도로들이 주어진다. 도로가 만들어지고 없어지는 계획에 대한 정보가 주어진다. 계획이 주어질 때마다 수도까지 몇 개의 도시를 방문해야 갈 수 있는지 구하는 문제이다. 도시마다 연결된 정보를 이차원배열에 넣었다. 계획이 주어질 때마다 이차원배열을 업데이트하고 bfs탐색을 통해 수도 1부터 도시까지 얼마나 걸려서 갈 수 있는지 체크하여 배열에 담아 반환했다. 메모리: 49952KB시간: 1232ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n; static int[][] city; static StringBui.. 2024. 6. 20. [백준] 23747: 와드 - JAVA https://www.acmicpc.net/problem/23747 풀이이 문제는 보드 위에서 이동과 와드 설치를 처리하는 문제로, 주어진 명령에 따라 보드의 상태를 변화시켜야 한다. W 명령을 수행하여 해당 위치와 인접한 같은 타입의 영역을 방문 처리하고, 상하좌우 이동을 통해 요리사의 위치를 업데이트했다. 최종적으로 방문한 위치를 '.'으로 표시하고, 방문하지 않은 위치를 '#'으로 표시하여 결과를 출력했다. 메모리: 127596KB시간: 720ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int r, c; static char[][] board; static boolean[][] result;.. 2024. 6. 10. [백준] 15591: MooTube (Silver) - JAVA https://www.acmicpc.net/problem/15591 풀이N번까지 번호를 가진 동영상들이 서로 연결되어있다. 연결마다 유사도가 k의 값으로 정해져 있다. 경로를 연결하여 유사도들 중 최소값이 두 동영상의 유사도가 된다. 특정 값을 정해 유사도가 그 값 이상인 동영상들의 개수를 묻는 문제이다. 시작 정점으로 할 동영상의 번호와, 특정 값이 주어지면 bfs탐색을 진행했다. 연결된 노드들을 탐색하여 유사도가 특정 값 K 이상일 때 카운트를 1증가시키며 큐에 넣어 계속했다. 메모리: 80360KB시간: 1008ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int v;.. 2024. 5. 20. [백준] 15971: 두 로봇 - JAVA https://www.acmicpc.net/problem/15971 풀이두 로봇이 서로 통신하기 위해서는 서로 인접한 지역에 있어야 한다. a구역에 있는 로봇과 b구역의 로봇에 서로 통신할 수 있는 지역으로 이동할 때 이동해야하는 거리의 최솟값을 구해야 한다. 생각한 풀이방법은 먼저 a지역에서 b지역까지 이동하고, 그 중 거리가 가장 큰 구간을 빼주는 것이다. dfs를 통해 int배열에 이동한 구역의 거리를 기록했고, 이 배열을 방문처리용도로 사용했다. 메모리: 80360KB시간: 1008ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int v; int cost.. 2024. 5. 19. [백준] 14395: 4연산 - JAVA https://www.acmicpc.net/problem/14395 풀이정수 s를 t로 바꾸는 최소 연산 횟수를 구한다. 연산은 `+, -, *, /` 를 사용할 수 있다.' 가능한 방법이 여러가지면 사전순으로 하나를 출력해야 하기 때문에 아스키 코드 순서인 `*, +, -, /` 순으로 탐색하였다. s와 t가 10의 9제곱까지 주어지므로 최대 LIMIT을 1,000,000,000으로 잡았다. 탐색중에 이 범위를 넘지 않는 연산만 진행했다. `/` 연산의 경우 숫자가 0이 아닐때만 사용가능하므로 처리해주었다. bfs 탐색을 통해 가장 먼저 나오는 결과를 출력하면 끝. 메모리: 14424KB시간: 132ms언어: Java 11import java.io.*;import java.util.*;public c.. 2024. 5. 19. [백준] 29703: 펭귄의 하루 - JAVA https://www.acmicpc.net/problem/29703 풀이펭귄의 현재 위치 S에서 출발하여, 물고기 서식지 F 중 한 곳을 지나, 펭귄의 집 H로 가는 최단 시간을 구하는 문제이다. 두 번의 bfs를 통해 해결했다. S부터 시작하는 bfs를 통해 출발지부터 물고기 서식지들 까지의 시간을 저장했다. H부터 시작하는 bfs를 통해 H에서 F까지 얼마나 걸리는 지 저장했다. S -> F, F -> H 의 시간이 각각 저장된 배열들을 이용해 어떤 F를 지났을 때 두 값의 합이 최소가 되는지 구했다. 메모리: 124844KB시간: 708ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] vect.. 2024. 5. 19. [백준] 17471: 게리맨더링 - JAVA https://www.acmicpc.net/problem/17471 풀이구역들이 서로 어떻게 연결되어있는지 주어진다. 구역들을 2개의 그룹으로 나눠, 각각의 인구수의 합의 차가 최소가 되게 해야한다. 그룹들은 서로 연결되있어야한다. 먼저, n개의 지역을 2개의 그룹으로 나눴다. 나눠진 그룹안의 지역들이 서로 연결되어 있는지 체크 후, answer를 갱신해주었다. 메모리: 16012KB시간: 160ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, answer; static int[] population; static ArrayList> graph; static boolean[] sel;.. 2024. 5. 19. [백준] 1039: 교환 - JAVA https://www.acmicpc.net/problem/1039 풀이정수 N의 i번 위치와 j번 위치의 숫자를 바꿀 수 있다. 이 행위를 K번 반복할 때 최댓값을 구해야 한다. 위치를 바꿀 때 바꾼 수가 0으로 시작하면 안된다. n번 수행했을 때 나온 수를 방문처리 하기 위해 이차원 배열로 방문처리했다. bfs탐색을 통해 숫자와 바꾼 횟수를 저장해가면 진행했다. 메모리: 54616KB시간: 244ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final int MAX = 1_000_001; static int answer; static class Node { int num; .. 2024. 5. 18. 이전 1 2 3 4 다음