본문 바로가기

그래프탐색24

[Baekjoon] 10026 - 적록색약 📝 문제 🔑 풀이 과정 · 연결요소의 개수를 구하는 문제. 근데 이제 적록색약이 아닌 사람이 봤을때의 연결요소의 개수와, 적록색약인 사람이 봤을때의 연결요소의 개수 총 두 가지 케이스를 구해야 하는 문제. · BFS 메서드는 하나로 만들고, 적록색약X인 사람이 봤을때의 배열, 적록색약O인 사람이 봤을때의 배열 총 2개를 사용했다. 🔓 답안 import java.io.*; import java.util.LinkedList; import java.util.Queue; public class Main { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static int N; static boolean[][] visited; public s.. 2023. 9. 6.
[Baekjoon] 14940 - 쉬운 최단거리 📝 문제 🔑 풀이 과정 · 기본적인 BFS 문제. 각 지점에서 목표지점까지의 거리 = 목표지점에서 각 지점으로의 거리 이므로, 목표지점을 시작점으로 BFS를 수행하면 된다. · 출력 부분을 잘 보면 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력하라 되어있다. 예제 입력에는 이 부분이 없어서 놓칠 수 있으니 주의하자. · 나 같은 경우는 n, m이 최대 1000이라 매우 작기때문에 전체탐색을 해도 시간초과가 나지 않을거라 생각하였고, BFS 완료 후 방문배열과 입력배열을 전체탐색해서 방문배열이 false고, 입력배열이 갈 수 있는 땅(1)인 곳은 -1을 넣어줬다. · 아니면 출력을 할 때 위 같은 조건이면 -1, 아니면 결과배열의 값을 출력하기. 이런식으로 진행해도 된다, 🔓 답안.. 2023. 9. 6.
[Baekjoon] 21736 - 헌내기는 친구가 필요해 📝 문제 🔑 풀이 과정 · 그냥 흔한 2차원 배열 BFS 문제. · 배열이 char형이라는 것과, 시작점의 위치도 내가 정해줘야 한다는 것이 다른문제와의 차이점이다. · 풀이 생략 🔓 답안 import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static int N; static int M; static char[][] campus; static boolean[][] visited; static int count = 0;.. 2023. 8. 23.
[Baekjoon] 1325 - 효율적인 해킹 📝 문제 🔑 풀이 과정 · 처음에는 예제 1이 출력이 어떻게 1, 2 나오는지 조차 이해를 못했다. 그러나 항상 그렇듯이 문제에 답이 있다. "A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다." 즉, A가 B를 신뢰하는 경우에는 B에서 A로 향하는 단방향 그래프가 생성된다는 의미이다. · 예제 1을 그림으로 표현하면 다음과 같다. 1을 해킹하면 3, 4, 5 도 다같이 해킹, 2를 해킹하면 3, 4, 5도 다같이 해킹, 3을 해킹하면 4, 5 해킹 4와 5는 해킹할때 같이 해킹되는 컴퓨터 없음. 즉 예제1의 출력이 1, 2가 되는 것이다. · N이 10,000으로 작은 편이므로 각 노드마다 BFS를 실행해준다. 물론 할때마다 방문배열 초기화는 필수다. 그리고 각 컴퓨터 해킹 시.. 2023. 8. 15.
[Baekjoon] 18352 - 특정 거리의 도시 찾기 📝 문제 🔑 풀이 과정 · 그래프를 탐색하는 문제. BFS를 사용해서 풀이했다. · 최단 거릿값을 저장하는 moves 배열을 사용했다. BFS를 사용해서 이전 도시의 최단 거릿값 + 1 을 moves 배열에 저장하는 방식을 사용했다. · 탐색 완료 후, moves 배열을 전체탐색 하면서 K값과 같은 값이 존재하면, 그 인덱스를 answer 라는 이름의 ArrayList에 저장했다. 그 후 ArrayList의 크기가 0이면 -1을 출력하고, 요소가 존재한다면 그 요소들을 출력하게 했다. · 주석을 보면 전체적인 과정이 이해갈 것이다. 🔓 답안 import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util... 2023. 8. 14.
[Baekjoon] 2583 - 영역 구하기 📝 문제 🔑 풀이 과정 · 이 문제는 DFS, BFS 어느 방법으로도 가능하다. 최근에 거의 BFS만 해서, 이번엔 DFS로 풀어봤다. (처음에 기억 안남 ㅋ) · 이 문제는 DFS, BFS 문제를 좀 풀어봤다면 쉬울것이다. 그냥 연결요소의 개수를 구하는 문제라 생각하면 된다. 다만 이제 그 연결요소마다의 넓이를 구해야한다는게 추가됐다는 점? · 풀이 과정 ① K개의 직사각형의 양 꼭짓점 정보를 받으면서, 직사각형 내부는 값을 1로 바꿔준다. ② N * M 만큼 배열 전체탐색 하면서, 값이 0이고 (직사각형에 포함이 안되고) 방문하지 않은 곳을 발견하면 거기서 부터 DFS를 해준다. 한 번 DFS를 하면 그 영역이 탐색완료될 것이다. ③ 우리는 영역의 크기를 구해야 하므로, DFS 메서드가 한 번 수행될.. 2023. 8. 11.

티스토리툴바