깊이우선탐색15 [Baekjoon] 1012 - 유기농 배추 📝 문제 🔑 풀이 과정 이 문제는 어제 풀었던 2667번 문제랑 사실상 똑같다고 볼 수있다; 그냥 2차원 배열내에서 연결요소의 개수를 구하는 것. 2667번 풀이가 궁금하다면 클릭 실버1인 2667번 문제가 문자열인 입력값을 int형 배열에 넣을 때 변환해주는것과 각 연결요소의 크기를 따로 구해야 한다는 점에서 더 어렵다?고 볼 수 있다. 실버2인 이 문제는 테스트 케이스가 여러개 일 뿐, 연결요소의 개수만 구해주면 된다. 오히려 이 문제는 변수가 T, M, N, K, X, Y 등 너무 다양하게 나와서 변수명을 선택하는게 더 어려웠다; 풀이는 생략 🔓 답안 import java.io.*; import java.util.LinkedList; import java.util.Queue; import java... 2023. 7. 4. [Baekjoon] 2667 - 단지번호붙이기 📝 문제 ❗ 주의 · charAt()의 반환형은 char형이다. 그러므로 int형 배열에 그대로 넣으면 안된다. -'0'을 꼭 해서 넣어주자. 안그러면 0은 48, 1은 49의 값으로 들어간다. 🔑 풀이 과정 예전 연결 요소의 개수 문제를 2차원으로 만든듯한 문제. · 우리가 구해야 할 것: 총 단지의 수, 그리고 단지내 집의 수를 오름차순으로 정렬한 것! 단지내 집의 수를 정렬을 해야하므로 따로 저장할 자료구조가 필요하다. · 이 문제는 DFS, BFS 다 가능한데, 나는 BFS방식으로 풀이했다. · 총 단지의 수는, N*N 크기의 지도를 순회하면서, 값이 1이고(집이 있는 경우) 방문 배열이 false일때 단지의 수를 하나씩 증가시켰다. ① 값이 0일때: 집이 없다는 뜻으로 pass ② 값이 1이고,.. 2023. 7. 3. [Baekjoon] 24480 - 알고리즘 수업 - 깊이 우선 탐색 2 📝 문제 🔑 풀이 과정 이 문제는 24479번 문제 - [알고리즘 수업 - 깊이 우선 탐색 1] 와 다른 조건은 다 똑같고, 인접 정점을 내림차순으로 방문한다는 조건만 다른문제. 24479번 풀이는 여기 ↓ https://seohyun0916.tistory.com/196 [Baekjoon] 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 📝 문제 🔑 풀이 과정 이 문제는 제목이랑 문제만 보고 베이직한 문제라 생각해서 바로 풀었는데, 꽤 많은 시도를 거친... 문제이다. 알고리즘 자체는 문제에 다 나와있는대로 풀면 되고, 기본 seohyun0916.tistory.com ① 인접리스트를 내림차순 정렬해준다. ArrayList를 내림차순 정렬하려면 Collections.sort(리스트명, Collectio.. 2023. 3. 30. [Baekjoon] 24479 - 알고리즘 수업 - 깊이 우선 탐색 1 📝 문제 🔑 풀이 과정 이 문제는 제목이랑 문제만 보고 베이직한 문제라 생각해서 바로 풀었는데, 꽤 많은 시도를 거친... 문제이다. 알고리즘 자체는 문제에 다 나와있는대로 풀면 되고, 기본적인 DFS 문제이다. ① 정점의 수(N)이 10만으로 매우 크기 때문에, 인접 행렬로 그래프를 표현하면 메모리초과 에러 발생 인접리스트로 표현해주자. ② 정점의 수(N)과 간선의 수(M)을 혼동하지 말고 잘 사용할 것. 간선의 수(M)은 M개의 줄을 입력받을 때 말고는 사용하지 않는다. 그 외 그래프 선언, 정렬, 출력 등은 모두 N을 사용한다. (예제 입력은 N, M 둘 다 5라서 이 에러를 잡아내기 힘들다.) ③ 인접 정점을 오름차순으로 방문한다는 조건이 있으므로, 입력을 받은 뒤 인접리스트 배열을 오름차순으로 .. 2023. 3. 28. [Baekjoon] 2644 - 촌수계산 📝 문제 🔑 풀이 과정 예제 입력1, 2의 촌수관계를 그래프로 나타내면 다음과 같다. (예제1, 2 동일) 여기서 a에서 b까지 갈 때의 간선의 수가 a와 b의 촌수이다. 예제 1) 7과 3의 촌수는? 3 예제 2) 8과 6의 촌수는? 친척 관계가 전혀 없음. ① DFS를 사용해서 풀이를 진행한다. ② DFS를 진행할 때, 방문 정점만을 가지는게 아니라, 현재 깊이인 depth 인자를 추가해준다. 깊이는 시작 노드가 0이고, 선을 하나 건널때 마다 1씩 증가시킨다. 그림 참고(시작이 7, 도착이 3일 때의 답은 3) ③ DFS를 진행하다가, 도착노드에 도달하면 현재 depth를 출력한다. 만약 관계가 없으면 -1을 출력한다. 🔓 답안 import java.io.*; import java.util.Stri.. 2023. 3. 27. [Baekjoon] 1260 - DFS와 BFS 📝 문제 ❗ 주의 ① 문제의 조건 중 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 → 나 같은 경우는 인접행렬을 사용해서 큰 상관이 없었지만, 인접리스트를 사용하는 경우 정렬 과정이 필요하다. ② DFS 수행 후, BFS 수행 전에 방문배열을 꼭 초기화 해주어야 한다. 🔑 풀이 과정 기본적인 DFS & BFS 문제 DFS는 재귀를 사용하여 구현했으며, BFS는 큐를 사용하여 구현했다. 🔓 답안 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import ja.. 2023. 2. 13. 이전 1 2 3 다음
