본문 바로가기

깊이우선탐색15

[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] 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] 2583 - 영역 구하기 📝 문제 🔑 풀이 과정 · 이 문제는 DFS, BFS 어느 방법으로도 가능하다. 최근에 거의 BFS만 해서, 이번엔 DFS로 풀어봤다. (처음에 기억 안남 ㅋ) · 이 문제는 DFS, BFS 문제를 좀 풀어봤다면 쉬울것이다. 그냥 연결요소의 개수를 구하는 문제라 생각하면 된다. 다만 이제 그 연결요소마다의 넓이를 구해야한다는게 추가됐다는 점? · 풀이 과정 ① K개의 직사각형의 양 꼭짓점 정보를 받으면서, 직사각형 내부는 값을 1로 바꿔준다. ② N * M 만큼 배열 전체탐색 하면서, 값이 0이고 (직사각형에 포함이 안되고) 방문하지 않은 곳을 발견하면 거기서 부터 DFS를 해준다. 한 번 DFS를 하면 그 영역이 탐색완료될 것이다. ③ 우리는 영역의 크기를 구해야 하므로, DFS 메서드가 한 번 수행될.. 2023. 8. 11.
[Baekjoon] 2468 - 안전 영역 📝 문제 🔑 풀이 과정 · 이 문제도 앞서 풀어본 문제들과 같이 기본적으로 연결요소의 개수를 구하는 것이다. 그러나 지금까지는 연결요소의 개수를 한 번만 구했다면, 이 문제는 비의 양에 따른 모든경우에서의 연결 요소의 개수를 구하고, 그 중에서 최대인 것을 찾는 것이다. · 그래서 각 경우의 연결요소 개수를 세는 count 변수를 두고, max라는 변수를 둬서 연결요소의 최댓값을 저장하고, 탐색이 이 다 끝난뒤 출력한다. · 각 경우마다 탐색을 하기 전에 방문배열을 초기화 시켜줘야 한다. · BFS 메서드의 인자에 시작점의 x, y 좌표 뿐 아니라 어느 높이까지 잠기는지에 대한 인자도 넣어주었다. 인자가 h라면 높이가 h이하인 지점이 잠김 → h 초과인 범위를 탐색하면 된다. · 높이가 1이상 100이하.. 2023. 7. 13.
[Baekjoon] 4963 - 섬의 개수 📝 문제 🔑 풀이 과정 지금까지 많이 풀었던 연결 요소의 갯수를 구하는 문제이다. 다만 지금까지는 상하좌우 총 4가지 방향을 탐색했다면, 이번에는 대각선 4방향까지 더해서 총 8가지 방향을 탐색해야 한다. 나는 BFS(너비 우선 탐색)로 풀었고, 풀이는 생략 🔓 답안 import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1}; static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1}; static int[][] arr; static bo.. 2023. 7. 12.

티스토리툴바