[1238] Contact

✔ Contact

[SWEA 1238]

문제 분석하기

시작점에서부터 시작하여 BFS를 수행하면서 방문할 경우 현재 방문 깊이를 저장

가장 방문 깊이가 깊은 것들 중에서 가장 숫자가 큰 사람을 반환

손으로 풀어보기

1. 인접 리스트로 노드와 간선의 그래프를 표현
2. BFS 탐색 알고리즘으로 탐색을 수행하면서 각 노드로 가는 거리값(방문 깊이)을 방문 배열에 저장
   • 이때 가장 먼 거리를 저장
3. 탐색 종료 후 방문 배열에서 값이 가장 먼 거리를 찾음
4. 가장 먼 거리를 갖는 숫자 중, 가장 큰 숫자를 반환

슈도코드 작성하기

T(테스트 케이스 수) = 10
for(T만큼) {
    N(입력 받는 데이터의 길이)
    S(시작점)
    A(그래프 데이터 저장 인접 리스트)
    visited(방문 거리 저장 배열)
    depth(가장 먼 거리)
    for(100만큼 반복하기) {
        A 인접 리스트의 각 ArrayList 초기화하기
    }
    for(N/2만큼 반복하기) {
        A 인접 리스트에 그래프 데이터 저장하기
    }
    visited 배열 초기화하기
    depth 초기화하기
    BFS(S) 실행하기
    answer(가장 큰 숫자) = 0
    for(100만큼 반복하기) {
        if(visited[i] == depth) {
            answer = Math.max(answer, i)
        }
    }
    #T와 answer 반환
}

BFS {
    큐 자료구조에 출발 노드 더하기(add 연산)
    visited 배열에 현재 노드 방문 기록하기
    while(큐가 빌 때까지) {
        큐에서 노드 데이터를 가져오기(poll 연산)
        현재 노드의 연결 노드 중 방문하지 않은 노드로
        이전 노드의 방문 노드 거리 + 1
        depth 갱신
        큐에 데이터 삽입(add 연산)
    }
}

코드 구현하기

/**
 * 1238) Contact
 */
public class D002_1238 {
    // A(그래프 데이터 저장 인접 리스트)
    static ArrayList<Integer>[] A;
    // visited(방문 거리 저장 배열)
    static int visited[];
    // depth(가장 먼 거리)
    static int depth;

    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스 수) = 10
        int T = 10;
        // T만큼
        for (int test_case = 1; test_case <= T; test_case++) {
            // N(입력 받는 데이터의 길이)
            int N = sc.nextInt();
            // S(시작점)
            int S = sc.nextInt();
            // A 인접 리스트의 각 ArrayList 초기화하기
            A = new ArrayList[101];
            for (int i = 0; i <= 100; i++) {
                A[i] = new ArrayList<Integer>();
            }
            // A 인접 리스트에 그래프 데이터 저장하기
            for (int i = 0; i < N / 2; i++) {
                int start = sc.nextInt();
                int end = sc.nextInt();
                A[start].add(end);
            }
            // visited 배열 초기화하기
            visited = new int[101];
            for (int i = 0; i <= 100; i++) {
                visited[i] = -1;
            }
            // depth 초기화하기
            depth = 1;
            // BFS(S) 실행하기
            BFS(S);
            // answer(가장 큰 숫자)
            int answer = 0;
            for (int i = 0; i <= 100; i++) {
                // 가장 먼 거리와 동일하다면
                if (visited[i] == depth) {
                    // 가장 큰 숫자로 갱신
                    answer = Math.max(answer, i);
                }
            }
            // #T와 answer 반환
            System.out.println("#" + test_case + " " + answer);
        }
    }

    // BFS
    private static void BFS(int Node) {
        // 큐 자료구조에 출발 노드 더하기(add 연산)
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(Node);
        // visited 배열에 현재 노드 방문 기록하기
        visited[Node]++;
        while (!queue.isEmpty()) {
            // 큐에서 노드 데이터를 가져오기(poll 연산)
            int now = queue.poll();
            // 현재 노드의 연결 노드 중 방문하지 않은 노드로
            for (int i : A[now]) {
                if (visited[i] == -1) {
                    // 이전 노드의 방문 노드 거리 + 1
                    visited[i] = visited[now] + 1;
                    // depth 갱신
                    depth = Math.max(depth, visited[i]);
                    // 큐에 데이터 삽입(add 연산)
                    queue.add(i);
                }
            }
        }
    }
}