DFS, BFS 문제 풀이 상세

이 문제의 핵심은 친구 관계를 그래프로 생각하고, 한 사람(시작 정점)에서 다른 사람(목표 정점)까지 경로가 존재하는지 확인하는 것입니다.

먼저, 두 풀이에서 공통으로 사용할 그래프 구성 부분을 보겠습니다. 친구 관계는 양방향이므로, A와 B가 친구라면 그래프에 A -> B와 B -> A 간선을 모두 추가해야 합니다.

Java

 

import java.util.*;

public class FriendshipChecker {

    // 친구 관계 데이터를 기반으로 그래프(인접 리스트)를 생성하는 헬퍼 메서드
    private static Map<String, List<String>> buildGraph(String[][] friendships) {
        Map<String, List<String>> graph = new HashMap<>();

        for (String[] friendship : friendships) {
            String person1 = friendship[0];
            String person2 = friendship[1];

            // 각 사람을 키로, 친구 리스트를 값으로 초기화
            graph.putIfAbsent(person1, new ArrayList<>());
            graph.putIfAbsent(person2, new ArrayList<>());

            // 양방향으로 친구 관계를 추가
            graph.get(person1).add(person2);
            graph.get(person2).add(person1);
        }
        return graph;
    }

    // ... (DFS 및 BFS 풀이 코드가 여기에 위치) ...

    public static void main(String[] args) {
        // 친구 관계 데이터 정의
        String[][] friendships = {
            {"A", "B"}, {"B", "C"},
            {"D", "E"}, {"E", "F"},
            {"G", "H"}
        };

        // 그래프 생성
        Map<String, List<String>> graph = buildGraph(friendships);

        // --- 문제: A와 C는 친구 관계인가? (예상: true) ---
        System.out.println("### A와 C는 친구 관계인가? ###");
        boolean resultDFS1 = solveWithDFS("A", "C", graph);
        System.out.println("DFS 결과: " + resultDFS1); // 예상: true

        boolean resultBFS1 = solveWithBFS("A", "C", graph);
        System.out.println("BFS 결과: " + resultBFS1); // 예상: true
        System.out.println("---------------------------\n");


        // --- 문제: A와 F는 친구 관계인가? (예상: false) ---
        System.out.println("### A와 F는 친구 관계인가? ###");
        boolean resultDFS2 = solveWithDFS("A", "F", graph);
        System.out.println("DFS 결과: " + resultDFS2); // 예상: false

        boolean resultBFS2 = solveWithBFS("A", "F", graph);
        System.out.println("BFS 결과: " + resultBFS2); // 예상: false
        System.out.println("---------------------------");
    }
}

---

1. 깊이 우선 탐색 (DFS)을 이용한 풀이

**재귀(Recursion)**를 사용하여 한 경로를 끝까지 탐색하는 방식으로 구현합니다. 방문한 친구를 다시 방문하지 않도록 visited Set을 사용하는 것이 핵심입니다.

• 동작 방식: A에서 시작 -> A의 친구 B로 이동 -> B의 친구 C로 이동 -> 목표 C를 찾았으므로 true 반환!

Java

 

// (FriendshipChecker 클래스 내부에 추가)

/**
 * DFS를 사용하여 두 사람의 연결 관계를 확인하는 메서드
 * @param start 시작 사람
 * @param end 목표 사람
 * @param graph 친구 관계 그래프
 * @return 연결 여부 (true/false)
 */
public static boolean solveWithDFS(String start, String end, Map<String, List<String>> graph) {
    // 방문한 사람을 기록하기 위한 Set
    Set<String> visited = new HashSet<>();
    return hasPathDFS(start, end, graph, visited);
}

/**
 * DFS 재귀 헬퍼 메서드
 */
private static boolean hasPathDFS(String current, String end, Map<String, List<String>> graph, Set<String> visited) {
    // 1. 만약 현재 위치가 목표라면, 경로를 찾은 것이므로 true 반환
    if (current.equals(end)) {
        return true;
    }

    // 2. 현재 위치를 방문했다고 기록 (무한 루프 방지)
    visited.add(current);

    // 현재 사람의 친구 목록이 없는 경우 (그래프에 없는 사람일 경우)
    if (!graph.containsKey(current)) {
        return false;
    }

    // 3. 현재 위치의 모든 친구들을 확인
    for (String friend : graph.get(current)) {
        // 4. 아직 방문하지 않은 친구라면, 그 친구로부터 다시 탐색 시작
        if (!visited.contains(friend)) {
            // 5. 재귀 호출에서 true가 반환되면, 경로를 찾은 것이므로 즉시 true를 반환
            if (hasPathDFS(friend, end, graph, visited)) {
                return true;
            }
        }
    }

    // 6. 모든 친구를 확인했지만 목표에 도달하지 못했다면, 이 경로로는 갈 수 없음
    return false;
}

---

2. 너비 우선 탐색 (BFS)을 이용한 풀이

**큐(Queue)**를 사용하여 시작점과 가까운 친구들부터 차례대로 탐색하는 방식으로 구현합니다. 마찬가지로 visited Set을 사용하여 중복 방문을 방지합니다.

• 동작 방식: A를 큐에 넣음 -> A를 꺼내고 A의 친구 B를 큐에 넣음 -> B를 꺼내고 B의 친구 C를 큐에 넣음 -> C를 꺼내보니 목표이므로 true 반환!

Java

 

// (FriendshipChecker 클래스 내부에 추가)

/**
 * BFS를 사용하여 두 사람의 연결 관계를 확인하는 메서드
 * @param start 시작 사람
 * @param end 목표 사람
 * @param graph 친구 관계 그래프
 * @return 연결 여부 (true/false)
 */
public static boolean solveWithBFS(String start, String end, Map<String, List<String>> graph) {
    // 1. 탐색할 사람들을 담을 큐(Queue) 생성
    Queue<String> queue = new LinkedList<>();
    // 방문한 사람들을 기록할 Set 생성
    Set<String> visited = new HashSet<>();

    // 2. 시작점을 큐와 visited에 추가
    queue.add(start);
    visited.add(start);

    // 3. 큐가 빌 때까지 반복
    while (!queue.isEmpty()) {
        // 4. 큐에서 한 사람을 꺼냄
        String current = queue.poll();

        // 5. 꺼낸 사람이 목표와 같다면, 경로를 찾았으므로 true 반환
        if (current.equals(end)) {
            return true;
        }
        
        // 현재 사람의 친구 목록이 없는 경우 (그래프에 없는 사람일 경우)
        if (!graph.containsKey(current)) {
            continue;
        }

        // 6. 현재 사람의 모든 친구들을 확인
        for (String friend : graph.get(current)) {
            // 7. 아직 방문하지 않은 친구라면, 큐와 visited에 추가
            if (!visited.contains(friend)) {
                visited.add(friend);
                queue.add(friend);
            }
        }
    }

    // 8. 큐가 모두 비워질 때까지 목표를 찾지 못했다면, 연결되지 않은 것
    return false;
}

결론

두 방법 모두 동일한 문제("A와 C는 친구인가?")에 대해 true라는 정확한 결과를 내놓습니다.

• DFS는 하나의 경로를 깊게 파고드는 방식에 적합합니다.
• BFS는 시작점으로부터 가까운 순서로 넓게 탐색하며, 최단 경로를 찾는 문제에도 응용될 수 있습니다. (예: "A와 C는 최소 몇 다리를 건너야 하는가?")