본문 바로가기

깊이 우선 탐색19

[백준] 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.
[백준] 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.
[백준] 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.
[백준] 3109: 빵집 - JAVA https://www.acmicpc.net/problem/3109 풀이첫번째 열에서 마지막 열까지 파이프를 이어야한다. 이때 이동은 `{ -1, 1 }`, `{ 0, 1 }`, `{ 1, 1 }` 으로 할 수 있다. 탐색 방향 순서를 위에서부터 채우기 위해 -1, 0, 1 순으로 탐색한다. 배열에 방문했다는 체크를 하면서 탐색하며, 마지막까지 같다면 개수를 늘리고, `true`를 리턴한다. 실패할 경우 `false`를 리턴하여 종료한다. 방문 체크를 먼저 하고 탐색을 보냈기 때문에 실패한 칸은 다시 가보지 않아도 되게하여 시간초과를 해결할 수 있었다.  메모리: 34748KB시간: 400ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 19.
[백준] 2458: 키 순서 - JAVA https://www.acmicpc.net/problem/2458 풀이1 ~ n번 학생들에 대해 m개의 관계가 주어지는데, 각각의 관계에는 a번 학생이 b번 학생보다 작다는 것을 알려준다. 이 관계들을 이용해 자신이 몇 번째 등수인지 정확히 알 수 있는 사람의 수를 세는 문제이다. 모든 정점끼리 탐색을 해야하기 때문에 플로이드-워셜 알고리즘을 사용했다. 플로이드-워셜은 O(n^3)의 시간복잡도를 갖는다. 핵심 로직은 다음과 같다.for (int k = 0; k i와 k가 연결되어있고, k와 j가 연결되어 있다면, i와 j는 연결되었다고 보는 것이다. 모든 정점끼리 연결 여부를 체크했다면 각 학생별로 연결된 학생의 수가 n-1인지 확인하면 된다.  메모리: 36932KB시간: 604ms언어: Java 11.. 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.
[백준] 16724: 피리 부는 사나이 - JAVA https://www.acmicpc.net/problem/16724 풀이N * M 지도에 U, D, L, R이 주어진다. 각 칸에서 어느 방향으로 한 칸 이동할 수 있는지를 나타낸다. 각 칸에서 이동시키기 편하게 하기 위해 U, D, L, R을 0, 1, 2, 3으로 치환하여 저장했다. 방문처리가 안된 칸에서부터 dfs를 시작하여 이동할 수 있는 칸을 지날때 union메서드를 통해 같은 그룹으로 묶어주었다. 최종적으로 그룹의 수를 구하면 답이 된다.  메모리: 72688KB시간: 560ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[][] vector = { { -1, 0 }, { 1, 0 }, { 0, .. 2024. 5. 19.

티스토리툴바