DFS32 [백준] 1926번 - 그림 [Java] https://www.acmicpc.net/problem/1926 1. 아이디어 BFS와 DFS를 활용해서 간단하게 해결할 수 있다.2. 문제풀이 입력을 받은 후 2중 for문으로 도화지를 순회하며 그림을 발견하면 BFS 또는 DFS 알고리즘으로 그림의 크기를 구했다. 이후 개수를 세주고 그림의 최대 크기를 저장하는 max 변수와 비교 갱신하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1}; public static void main(.. 2025. 1. 17. [백준] 2667번 - 단지번호붙이기 [Java] https://www.acmicpc.net/problem/2667 1. 아이디어 단지를 하나의 그래프로 생각해서 BFS와 DFS를 활용해서 해결했다.2. 문제풀이 입력을 받은 후 2중 for문으로 지도를 순회하며 집을 발견하면 BFS 또는 DFS로 연결된 다른 집을 모두 탐색하며 개수를 세면 단지 하나에 포함된 집의 수를 셀 수 있다. 같은 집을 방문하지 않게 방문 체크를 하며 진행했고, 단지마다 구한 집의 수는 우선순위 큐에 넣어서 정렬한 채로 출력하도록 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static .. 2025. 1. 17. [백준] 2606번 - 바이러스 [Java] https://www.acmicpc.net/problem/2606 1. 아이디어 BFS와 DFS 알고리즘으로 해결했다.2. 문제풀이 컴퓨터와 네트워크가 정점과 간선이 되는 그래프로 해석할 수 있고 1번 컴퓨터가 바이러스를 옮기는 것은 1번 정점에 연결된 다른 정점의 수를 구하는 것과 동일하다. 1번 컴퓨터를 제외하고 세는 것만 주의해서 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.. 2025. 1. 17. [백준] 1260번 - DFS와 BFS [Java] https://www.acmicpc.net/problem/1260 1. 아이디어 문제 이름 그대로 DFS와 BFS로 풀면 된다.2. 문제풀이 DFS와 BFS의 기본 구현을 할 수 있으면 해결할 수 있는 문제로 인접리스트 기반으로 구현했다. 출력을 위해 StringBuilder를 정적 변수로 사용해서 활용했고, 번호가 작은 정점을 우선으로 방문하기 위해 인접리스트를 한번 정렬해줘야 한다.3. 코드 import java.io.*;import java.util.*;public class Main { private static final StringBuilder sb = new StringBuilder(); private static boolean[] visited; public static .. 2025. 1. 17. [백준] 11724번 - 연결 요소의 개수 [Java] https://www.acmicpc.net/problem/11724 1. 아이디어 주어진 입력으로 만들어질 수 있는 그래프의 개수를 구하는 문제로 BFS, DFS, Union-Find 알고리즘 3가지 방법으로 해결할 수 있었다.2. 문제풀이 BFS와 DFS는 주어진 입력으로 그래프의 연결관계를 나타내는 인접리스트와 각 정점을 방문했는지 표시하는 방문 체크 배열을 만든 후 반복문으로 각 정점을 순회하며 방문한 정점이면 넘어가고 방문하지 않은 정점이면 탐색으로 그래프의 개수를 세는 방식으로 구현했다. Union-Find는 인접리스트를 만드는 대신 바로 집합 연결을 해주었다. 이후 각 정점이 집합의 그룹장인지 여부만 세면 간단하게 그래프의 개수를 구할 수 있다.3. 코드 import java.io.*;im.. 2025. 1. 17. [백준] 22869번 - 징검다리 건너기 (small) [Java] https://www.acmicpc.net/problem/22869 1. 아이디어 BFS, DFS, 다이나믹 프로그래밍 3가지 방법으로 해결했다.2. 문제풀이 - BFS해당 문제는 각 돌을 노드로 이동할 수 있는 돌에는 간선을 연결한다 했을 때 1번 노드에서 N번 노드를 방문할 수 있는지 BFS 알고리즘으로 파악할 수 있다. 이때 항상 오른쪽으로만 이동해야 하므로 유방향 간선 그래프가 됨에 주의해야 한다. - DFS1번 돌부터 시작하며 재귀는 현재 돌보다 숫자가 큰 돌들을 비교하며 방문할 수 있는 돌이면 방문하는 과정을 반복하고 방문 체크를 해줬다. 이후 N번 돌이 방문 체크가 되어있는지 확인하면 간단하게 구현할 수 있다. - 다이나믹 프로그래밍dp 배열은 갈 수 있는 돌을 체크한다. 1번 돌부터 반복.. 2025. 1. 15. [백준] 1520번 - 내리막 길 [Java] https://www.acmicpc.net/problem/1520 1. 아이디어 Top-Down 다이나믹 프로그래밍을 활용하면 경로의 개수를 구할 수 있다.2. 문제풀이 특정 위치에서 도착 지점까지 갈 수 있는 경로의 개수는 특정 위치 상하좌우에 위치한 내리막길에서 도착지점까지 갈 수 있는 경로의 개수의 합이다. 이를 dfs로 도착 지점이면 1을 반환하고 도착 지점이 아니면 상하좌우에 내리막길에서 경로의 개수를 더해서 반환하도록 짜면 로직은 구현이 된다. 시간 초과 문제를 해결하기 위해 메모이제이션을 해야하는데 지도와 같은 크기의 2차원 dp 배열을 선언하고 dp 배열에는 특정 위치에서 도착 지점에 갈 수 있는 경로의 개수를 저장한다. 이후 dfs에서 dp 배열에 경로가 저장되어 있으면 해당 개수를 반.. 2025. 1. 3. [백준] 20166번 - 문자열 지옥에 빠진 호석 [Java] https://www.acmicpc.net/problem/20166 1. 아이디어 격자의 크기와 신이 좋아하는 문자열의 길이가 작다는 점에서 깊이 우선 탐색을 이용할 수 있을 것 같았고 신이 좋아하는 문자열을 비교하는 횟수가 많고 중복될 수 있다는 점에서 미리 가능한 조합을 다 구하고 비교를 O(1)로 해결하도록 구현했다.2. 문제풀이 신이 좋아하는 문자열의 길이가 1 ~ 5 이므로 길이가 1인 문자열부터 길이가 5인 문자열까지 격자의 각 점에서 전부 dfs를 돌렸다.dfs과정에서 파라미터로 완성될 문자열을 StringBuilder로 들고 다니며 depth를 내려갈 때마다 뒤에 방문한 격자의 문자를 더하고 depth를 올라가면 다시 지우는 방식으로 가능한 모든 문자열 조합을 구해서 이를 HashMap에.. 2024. 12. 23. 이전 1 2 3 다음
