반응형 알고리즘/깊이 우선 탐색(dfs)7 백준 2644번 : 촌수계산 java 이 문제는 사람의 수를 입력받고 두 사람의 번호를 입력받아 두 사람이 몇 촌 관계인지를 확인하는 문제입니다. 이 문제를 풀기 위해서 사람들간의 촌수 관계를 인접 리스트에 저장한 후 dfs로 순회하면 됩니다. 시작점을 한 명의 번호로 두고 찾고자 하는 사람의 번호를 찾으면 return 하게 함수를 만들었습니다. 여기서 연결 리스트란 한 정점과 연결되어 있는 다른 정점들을 나타내는 방식입니다. 위의 그림과 같이 정점들이 연결되어 있다고 하겠습니다. 이 그래프를 인접 리스트로 나타내면 위와 같은 그림이 나옵니다. 임의의 정점에 어떤 정점들이 연결되어 있는지를 나타내는 방식이 인접리스트입니다. 이제 코드를 보여드리도록 하겠습니다. import java.io.*; import java.util.*; public .. 2022. 7. 7. 백준 1707번 : 이분 그래프 java 이 문제는 이분 그래프인지 아닌지를 확인하는 문제입니다. 우선 이분 그래프가 무엇인지에 대해서 설명드리겠습니다. 이분 그래프란 위의 그림과 같이 연결된 두 정점의 색깔을 다르게 칠할 수 있는 그래프입니다. 위의 그림과 같이 빨간 간선이 추가되어 연결된 두 노드의 색깔이 같다면 이는 이분 그래프라 말할 수 없습니다. 그래프가 이분 그래프인지 확인하는 방법은 dfs를 이용하는 방법과 bfs를 이용하는 방법이 있습니다. 저는 이 중에서 dfs를 이용하였습니다. 하나의 정점을 선택한 후 dfs를 이용하여 이동할 때 이동한 간선이 이전의 간선과 다른 타입으로 만들 수 있는지를 확인하면서 진행하였습니다. 이미 방문한 정점이라도 다른 타입인지를 확인하게 만들었습니다. 코드를 보여드리도록 하겠습니다. import ja.. 2022. 6. 30. 백준 1987번 : 알파벳 java 이 문제는 깊이 우선 탐색을 이용해서 칸을 이동하면서 같은 알파벳이 적힌 칸을 두 번 지나지 않고 최대 갈 수 있는 칸을 구하는 문제입니다. 이 문제에 대해서 그림을 통해 자세히 설명드리도록 하겠습니다. 예제 1번을 표에 나타내면 위의 그림과 같습니다. 저는 이 문제를 풀 때 이미 지나간 알파벳은 set에 저장하여 다시 지나가지 않도록 했습니다. ArrayList나 LinkedList는 contains 메소드에 대한 시간 복잡도가 O(n)입니다. 하지만 HashSet을 통해서 set을 구현하면 O(1)의 시간 복잡도로 contains 메소드를 사용 가능합니다. 따라서 set을 사용하지 않으면 시간 초과가 나므로 set을 사용하였습니다. 이 문제에서 시작점은 1행 1열이니 여기서 dfs를 시작합니다. 이제.. 2022. 6. 17. 백준 4963번 : 섬의 개수 java 이 문제는 dfs를 이용하여 연결되어 있는 땅들을 확인하여 섬의 개수를 세는 문제입니다. 이 문제를 푸는 과정을 그림을 통해 보여드리도록 하겠습니다. 아래의 그림은 문제에 나와있는 예시입니다. 이제 이 그림에서 섬이 몇 개가 있는지를 찾아보겠습니다. 우선 초록색으로 표시된 땅 주변에 연결된 땅들을 찾아서 하나의 섬으로 묶어보겠습니다. 위의 그림과 같은 순서로 섬 하나가 만들어졌습니다. 이제 연결된 땅이 없으므로 떨어져 있는 섬들을 찾아보겠습니다. 노란색으로 표시된 땅 근처에도 연결된 땅이 없기 때문에 섬 하나가 또 완성되었습니다. 파란색으로 표시된 땅 주변의 땅들을 탐색해보도록 하겠습니다. 이제 더 이상 탐색하지 않은 땅이 없습니다. 따라서 이 지도에서 섬의 개수는 3개입니다. 이제 코드를 보여드리도록 .. 2022. 6. 9. 백준 1967번 : 트리의 지름 java 이 문제는 dfs를 이용하여 노드들을 이동할 때 이동한 가중치의 합이 가장 크게 되는 경로의 가중치의 합을 출력하는 문제입니다. 위의 그림과 같이 트리가 있을 때 빨간 선으로 되어 있는 간선들의 가중치의 합이 가장 크므로 이러한 경로를 구하는 알고리즘입니다. 저는 이 문제를 해결하기 위해서 각 경로에서 dfs를 하여 가중치의 합이 가장 클 때를 찾았습니다. 코드를 보면서 추가로 설명드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main { static List[] map; static boolean[] visited; static int max = Integer.MIN_VALUE; static int n; public static void.. 2022. 6. 8. 백준 17070번 : 파이프 옮기기 1 java 이 문제는 파이프가 어디로 이동할 수 있는지를 확인해주면서 벽에 닿을 때만 제외해주면 되는 문제입니다. 이 문제를 풀 때 파이프가 현재 가로 방향에 있는지, 세로 방향인지, 대각선 방향인지에 따라서 경우를 나누어주면 됩니다. 파이프의 끝 점을 기준으로 문제를 푸는 과정을 그림으로 보여드리겠습니다. 위의 그림은 N이 4일 때를 나타냈습니다. 이제 이 파이프가 이동할 수 있는 경로를 찾아보겠습니다. 우선 오른쪽으로 파이프를 이동시키겠습니다. 이렇게 파이프가 위치하면 파이프가 가로 방향으로 위치해 있기 때문에 오른쪽과 오른쪽 대각선 아래 방향이 가능합니다. 이 두 방향으로 파이프를 이동시켜 보겠습니다. 파이프를 가로로 이동시켰을 때는 (4, 4)로 갈 수 없습니다. 하지만 대각선으로 파이프를 이동시켰을 때 세.. 2022. 6. 6. 백준 1182번 : 부분수열의 합 java 이 문제는 dfs를 이용한 백트래킹 문제입니다. dfs를 이용하여 입력받은 수열을 순회하면서 지금까지 입력받은 부분수열의 합이 S와 같아지면 경우의 수를 추가하면 됩니다. 코드를 보며 추가로 설명드리겠습니다. import java.io.*; import java.util.*; public class Main { static int N, S; static int[] numArr; static boolean[] visited; static int count = 0; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Stri.. 2022. 6. 6. 이전 1 다음 반응형
