본문 바로가기

그래프 탐색45

[백준] 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.
[백준] 19542: 전단지 돌리기 - JAVA https://www.acmicpc.net/problem/19542 풀이트리모양의 길 위에서 전단지를 돌리는데, 현재 노드에서 거리가 d이하인 노드들에는 현재 노드에서 전단지를 돌릴 수 있다. 따라서, 어떤 노드로부터 리프 노드까지의 거리가 d이하라면 더이상 앞으로 나아가지 않아도 된다는 것이다. dfs탐색을 통해 리프까지의 최대 거리를 구한다. 해당 거리가 d이상이라면 `cnt`값을 늘려줬다. 다시 시작 정점으로 돌아와야 하므로 `cnt * 2`가 정답이 된다.  메모리: 70564KB시간: 456ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int s, d, cnt; static ArrayList> g.. 2024. 7. 13.
[백준] 25195: Yes or yes - JAVA https://www.acmicpc.net/problem/25195 풀이방향그래프가 주어지고, 1번 정점에서 출발해 리프노드까지 도달해야한다. 이때, 팬클럽이 위치하는 정점들을 피해 리프노드까지 도달할 수 있는지 확인하는 문제이다. dfs탐색의 인자로 팬클럽을 만났는지 여부를 담아 진행했다. 리프노드에 갔을 때 팬클럽을 만난적이 없다면 boolean값을 갱신해준다. 방문처리를 하지 않고 진행했는데 그 이유는 주어진 그래프가 사이클이 없음이 보장되었고, 방문처리를 할 경우 1 -> 2 -> 4 의 루트로 여행했다면, 1 -> 3 -> 4 의 루트로 여행하는 것은 이미 4번 정점이 방문처리 되었기 때문에 진행이 안되는 문제가 있었기 때문이다. 따라서, 방문처리 없이 바로 이전 정점으로만 갈 수 없게 했다. .. 2024. 7. 13.
[백준] 21278: 호석이 두 마리 치킨 - JAVA https://www.acmicpc.net/problem/21278 풀이건물들이 도로로 연결되어있고, 2개의 건물을 골라 치킨집을 열어야 한다. 이때, 치킨집으로부터 각 건물들까지의 거리의 합이 최소가 되게 해야한다. 먼저 플로이드-워셜 알고리즘을 통해 각 건물들 사이의 거리를 구했다. for (int k = 1; k  건물들 사이의 거리를 구한 후, 2개의 건물을 정해 거리의 합을 계산해 정답을 갱신해주었다. 메모리: 17220KB시간: 192ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] dist; public static void main(String[.. 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.
[백준] 14267: 회사 문화 1 - JAVA https://www.acmicpc.net/problem/14267 풀이상사가 직속 부하를 칭찬할 수 있는데 a가 b에게 10의 칭찬을 했다면 b의 직속 부하인 c도 10의 칭찬을 받는 것이 된다. 각 번호의 직원마다 직속 상사의 번호가 주어져 저장했다. 직속 상사로부터 칭찬을 받은 직원의 번호와 칭찬 수치가 주어지는데, int배열을 만들어 저장했다. 1번이 사장이므로 1번부터 시작하여 트리를 타고 내려가면서 int배열의 값을 부모 노드에서 자식 노드에 더해주는 식으로 구현했다.  메모리: 76068KB시간: 792ms언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> list; static i.. 2024. 5. 19.