[백준] 1058. 친구

https://www.acmicpc.net/problem/1058

1. 플로이드워셜로 푸는 방법

플로이드워셜은 N개의 노드에서 N개의 노드로 이동하는데 걸리는 최단 거리(비용)을 구할 수 있다. 즉, 각 노드에서 다른 N-1개의 노드로 몇 번의 이동으로 도달 가능한지 구한 후(=사람 a와 사람 b의 관계), 1번 또는 2번으로 이동이 가능하면 2-친구 관계이므로 카운트해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        for (int i = 0; i < n; i++) {
            char[] arr = br.readLine().toCharArray();
            for (int j = 0; j < n; j++) {
                if (arr[j] == 'Y') {
                    map[i][j] = 1;
                } else {
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        // 플로이드워셜
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (map[i][k] != Integer.MAX_VALUE && map[k][j] != Integer.MAX_VALUE) {
                        map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                    }
                }
            }
        }

        // 각 사람의 2-친구 수 구하기
        int answer = 0;
        for (int i = 0; i < n; i++) {
            int friendCnt = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (map[i][j] == 1 || map[i][j] == 2) {
                    friendCnt++;
                }
            }
            answer = Math.max(answer, friendCnt);
        }

        System.out.println(answer);
    }
}

 

플로이드워셜을 사용했을 때 시간 복잡도는 최대 O(N^3)이므로 50^3이다.

2. BFS로 푸는 방법

BFS를 사용하여 특정 노드로부터 최대 2까지 떨어진 노드 수를 구하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        char[][] map = new char[n][n];

        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();
        }
        
        int answer = 0;

        // BFS
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[n];
            Queue<Node> que = new LinkedList<>();
            que.add(new Node(i, 0));
            visited[i] = true;
            int friendCnt = 0;

            while (!que.isEmpty()) {
                Node now = que.poll();
                friendCnt++;

                if (now.cnt < 2) {
                    for (int j = 0; j < n; j++) {
                        if (map[now.node][j] == 'Y' && !visited[j]) {
                            visited[j] = true;
                            que.add(new Node(j, now.cnt + 1));
                        }
                    }
                }
            }

            answer = Math.max(answer, friendCnt - 1); // -1을 하는 이유 = 자기 자신을 poll 한 경우는 빼기
        }

        System.out.println(answer);
    }

    static class Node {
        int node;
        int cnt;

        public Node(int node, int cnt) {
            this.node = node;
            this.cnt = cnt;
        }
    }
}

 

3. DFS로 푸는 방법

BFS로 푼 것처럼 DFS로도 풀 수 있다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static char[][] map;
    static boolean[] visited;
    static Set<Integer> friends;

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        map = new char[n][n];

        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();
        }

        int answer = 0;

        // DFS
        for (int i = 0; i < n; i++) {
            visited = new boolean[n];
            friends = new HashSet<>();
            
            visited[i] = true;
            dfs(i, 0);
            
            answer = Math.max(answer, friends.size() - 1); // set을 통해 2-친구 관계인 노드의 개수 계산
        }

        System.out.println(answer);
    }

    private static void dfs(int now, int cnt) {
        friends.add(now);
        
        if (cnt == 2) {
            return;
        }

        for (int i = 0; i < n; i++) {
            if (map[now][i] == 'Y' && !visited[i]) {
                visited[i] = true;
                dfs(i, cnt + 1);
                visited[i] = false; // 방문 처리 초기화
            }
        }
    }
}

 

이때 visited[i] = false 를 생략하면, 다음 상황에서 문제가 된다. 

• 1번 노드에서 출발했을 때 1 → 2, 2 → 3을 지나가서 결과적으로 1, 2, 3을 방문 처리한다. 
• 그리고 이어서 1 → 3을 지나려고 하는데 이미 3번 노드에 방문 처리가 되어있으므로 방문하지 않는다. 
• 따라서 1번 노드와 4, 5번 노드는 2-친구 관계이지만 4, 5번 노드를 방문하지 않는다.

따라서 visited[i] = false 를 통해 방문 처리를 초기화해줬다.

 

그런데 이렇게 하면, 1번 노드의 2-친구 관계가 몇명인지 알 수 있는 방법이 없다. visited 배열을 순회하며 true인 노드들이 몇개인지 탐색하려고 했으나, visited 배열을 초기화하므로 해당 방법은 유효하지 않다.

따라서 set에 2-친구 관계인 노드들을 담아주었다. 만약 1 → 2 → 3을 탐색하여 1, 2, 3을 방문하고, 이어서 1 → 3 → 4을 탐색하면, 3번 노드는 중복으로 방문하게 된다. 따라서 방문할 때마다 카운트를 해주면 중복으로 방문한 것까지 카운트된다. 따라서 중복을 허용하지 않는 set을 사용했다.