반응형 dfs31 [백준] 1707번 - 이분 그래프 (Java) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 먼저 이분그래프에 대해 알아보자. 2. 인접한 정점은 다른 색상으로 저장하자. (1 or 2) 3. 방문하려는데 동일한 색상이 이미 칠해져 있으면 이분그래프가 아니다. 4. DFS(정점번호, 색상)을 넘겨주자. import java.util.*; /* [백준] 1707번 - 이분 그래프 (Java) */ public class Main { static int K, V, E; static in.. 2022. 9. 13. [백준] 14502번 - 연구소 (Java)(△) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다. 2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다. 2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자. 3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수) 3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가.. 2022. 9. 12. [백준] 1520번 - 내리막 길 (Java) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. map에는 높이 정보가 주어지고, 탐색은 상하좌우로만 가능하다. 2. 경로를 찾는데 높이가 지금보다 낮은 쪽으로만 이동 가능한 경로를 찾는다. 3. 가능한 경로의 개수를 찾는다. 4. dfs 파라메터로 좌표 정보를 넘겨준다. import java.util.*; /* [백준] 1520번 - 내리막 길 (Java) */ public class Main { int N, M; int A[][]; bool.. 2022. 9. 7. [백준] 2644번 - 촌수계산 (Java) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 1. 부모-자식 관계지만 거슬러 올라갈 수 있으므로 방향이 없는 트리와 같다. 2. DFS 파라미터로 정점 번호와 count를 넘겨준다. 3. Y를 찾지 못하면 flag를 둬서 -1을 출력한다. import java.util.*; /* [백준] 2644번 - 촌수계산 (Java) */ public class Main { static int N, M, X, Y; ArrayList.. 2022. 9. 5. [백준] 2583번 - 영역 구하기 (Java) https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1. 입력데이터 스타일이 좀 특이하다. 직사각형의 대각선 꼭지점의 좌표가 2개 주어지는데 입력 받자마자 map에 사각형 넓이만큼 1로 채우자. 그런 다음 탐색을 통해서 빈공간의 갯수와 넓이를 구하면 된다. for (int i=0; i 2022. 9. 3. [백준] 11725번 - 부모의 트리찾기 (Java)(○) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net [첫번째] 1. 입력함수에서 인접행렬로 정점과 간선을 표현하자. 2. 방향이 없기 때문에 양쪽 모두 행렬로 표현해야 한다. 3. dfs 파라미터는 다음 정점 번호를 넘겨주자. 4. 1번의 루트 고정이므로 2번 정점부터 각 정점의 부모 노드가 뭔지 출력하면 된다. 5. 위의 출력 예제에서 2번 정점의 부모는 4번, 3번의 부모는 6번인 셈이다. 6. 1번부터 dfs 탐색을 해서 이미 방문한 노드가 부모인 셈이므로 그 번호를 출력하면 된다. 더보기 import j.. 2022. 9. 3. [백준] 1987번 - 알파벳 (Java)(○) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 1. 세로 R, 가로 C로 된 맵이 있고, 대문자 알파벳으로 채워져 있음. 2. (1, 1)에 말이 있는데 상/하/좌/우로 움직일 수 있음. 그런데 이동한 칸의 알파벳은 이전 위치의 알파벳들과 달라야지 이동이 가능함. 3. 칸을 지날 때 마다 알파벳을 저장하는 배열이 필요하고, 새 알파벳과 비교하는 함수가 필요함. 4. 방문배열도 당연히 필요함. 5. dfs함수 파라미터는 좌표를 넘겨주자... 2022. 9. 2. [백준] 2468번 - 안전영역 (Java)(○) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 빗물높이는 주어지지 않으니 1~100까지 증가시키면서 섬의 개수를 탐색해서 가장 큰 수를 도출하자. 2. 상/하/좌/우로 탐색하면서 DFS 함수 내부에서 빗물높이와 비교해서 낮으면 스킵하는 식으로 구현하자. 3. 아무지역도 물에 잠기지 않을 수도 있다가 뜻하는 케이스는? 1. 빗물높이를 1부터 시작해서 TC 중 실패하는게 있었다. 2. 아무지역도 물에 잠기지 않을수도 있다는 노트가 빗물높이를 0으로.. 2022. 9. 1. [백준] 10026번 - 적록색약 (Java)(○) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. R / G / B를 별도의 그룹으로 구분해서 탐색한 결과와 R과 G를 동일 그룹으로 묶어서 탐색한 결과를 도출하는 문제이다. 1. 상하좌우 탐색을 하는 DFS 알고리즘 문제이다. 2. DFS 함수를 2가지 종류로 만들어서 R/G/B를 모두 구분하는 함수와 R-G / B 로 구분하는 함수로 만들어서 순차적으로 호출한다. 더보기 import java.util.*; /* [백준] 10026.. 2022. 9. 1. 이전 1 2 3 4 다음 반응형
