Find Center of Star Graph2

✏️오늘의 문제

💡그래프와 경로 탐색: Java를 활용한 유효한 경로 찾기

1. 그래프란 무엇인가?

그래프는 점(노드)과 그 점들을 연결하는 선(간선)으로 구성된 데이터 구조입니다. 노드는 개별적인 요소를 나타내며, 간선은 두 노드 간의 관계를 나타냅니다. 그래프는 다양한 문제를 해결하는 데 유용하게 사용됩니다.

2. 그래프의 구성 요소

• 노드 (점): 그래프에서 개별적인 요소를 의미합니다. 예를 들어, 친구, 도시, 웹사이트 등이 노드가 될 수 있습니다.
• 간선 (선): 두 노드를 연결하는 선으로, 노드 간의 관계를 나타냅니다.

3. 그래프 표현 방법

그래프는 보통 두 가지 방법으로 표현됩니다:

• 인접 리스트: 각 노드에 대해 연결된 노드 목록을 저장합니다.
• 인접 행렬: 노드 간의 연결을 2차원 배열로 나타냅니다.

4. 유효한 경로 찾기 문제

주어진 노드와 간선 정보를 기반으로 두 노드 간의 경로가 존재하는지를 확인하는 문제입니다. 이 문제를 해결하기 위해 DFS(깊이 우선 탐색) 알고리즘을 사용할 수 있습니다.

5. Java 코드 예제

다음은 Java를 사용하여 두 노드 간의 유효한 경로를 찾는 코드 예제입니다:

import java.util.*;

public class Solution {
    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // 그래프 만들기
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.putIfAbsent(edge[1], new ArrayList<>());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        // 방문 체크를 위한 Set
        Set<Integer> visited = new HashSet<>();
        return dfs(graph, source, destination, visited);
    }

    private boolean dfs(Map<Integer, List<Integer>> graph, int current, int destination, Set<Integer> visited) {
        // 현재 점이 목표 점이면 true 반환
        if (current == destination) {
            return true;
        }

        // 현재 점을 방문했다고 기록
        visited.add(current);

        // 현재 점의 모든 이웃 점을 확인
        for (int neighbor : graph.get(current)) {
            // 이웃 점이 아직 방문하지 않았다면
            if (!visited.contains(neighbor)) {
                // 이웃 점에서 다시 DFS 탐색
                if (dfs(graph, neighbor, destination, visited)) {
                    return true;
                }
            }
        }

        // 모든 이웃 점을 확인했는데도 목표 점에 도달하지 못하면 false 반환
        return false;
    }
}

6. 코드 설명

• 그래프 생성: 주어진 간선 정보를 바탕으로 인접 리스트를 만들어 그래프를 구성합니다.
• DFS 탐색: 시작 노드에서 목표 노드까지의 경로를 탐색합니다. 현재 노드가 목표 노드와 같으면 true를 반환하고, 방문한 노드를 기록하여 무한 루프를 방지합니다.
• 이웃 탐색: 현재 노드의 모든 이웃 노드를 확인하고, 방문하지 않은 노드에 대해 재귀적으로 DFS를 호출합니다. 모든 이웃을 확인한 후에도 목표 노드에 도달하지 못하면 false를 반환합니다.

7. 결론

그래프는 복잡한 관계를 표현하고 분석하는 데 매우 유용한 데이터 구조입니다. DFS 알고리즘을 통해 두 노드 간의 유효한 경로를 찾는 문제를 해결할 수 있습니다. 이와 같은 기술은 다양한 분야에서 활용될 수 있으며, 문제 해결 능력을 향상시키는 데 기여할 것입니다.

이 글을 통해 그래프의 기본 개념과 경로 탐색 문제를 해결하는 방법에 대해 알아보았습니다. 그래프를 활용한 다양한 문제를 풀어보며 실력을 쌓아보세요!