문제 개요

그래프에서 BFS를 한 단계 진행했을 때 닿을 수 있는 노드들의 최대를 구하는 문제입니다.

문제 접근

문제가 정확히 요구하는 것이 무엇인지 파악하는 것이 제일 어려웠던 것 같습니다. 시작 노드와의 거리가 2보다 작거나 같은 모든 노드들의 개수를 구하는 것이 문제의 핵심이었던 것 같습니다.

이를 위해서 BFS를 응용하여 두번만 주변을 탐색하게 하였습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int n;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static char[][] matrix = new char[55][];
    private static boolean[] visited;

    private static void input() throws Exception {
        n = Integer.parseInt(bf.readLine());
        for (int i = 0; i < n; i++) {
            matrix[i] = bf.readLine().toCharArray();
        }
    }

    private static int searchFriends(int idx) {
        int friends = 0;
        for (int i = 0; i < n; i++) {
            if (matrix[idx][i] == 'Y' && visited[i] == false) {
                visited[i] = true;
                friends++;
            }
        }
        return friends;
    }

    static int stepBfs(int idx) {
        visited = new boolean[55];
        visited[idx] = true;
        int friends = searchFriends(idx);
        
        for(int i=0;i<n;i++){
            if(matrix[idx][i]=='Y'){
                friends += searchFriends(i);
            }
        }
        
        return friends;
    }

    static int process(){
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = Math.max(result, stepBfs(i));
        }
        return result;
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(process());
    }
}

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