[S2] 백준 1058번 친구 Java 너비 우선 탐색

리뷰

 

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

인접 행렬을 토대로 최대 depth가 2인 친구의 수를 구하는 문

 

 

전역 변수

• edges : 인접 리스트로 변환하기 위한 2차원 리스트

 

함수

static int bfs(int sn, boolean[][] relation) /*throws IOException*/ {
        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0;
        for (Integer i : edges.get(sn)) {
            q.add(i);
            relation[sn][i] = true;
            cnt++;

//            bw.write("현재 노드 : " + sn + "와 노드 " + i + "연결\n");
        }
        relation[sn][sn] = true;

        while (!q.isEmpty()) {
            int cn = q.poll();
            for (int nn : edges.get(cn)) {
                if (relation[sn][nn]) continue;
                relation[sn][nn] = true;
                cnt++;
//                bw.write("현재 노드 : " + sn + "와 노드 " + nn + "연결\n");
            }
        }
        return cnt;
    }

 

친구간의 관계를 매핑하고, 친구의 수를 출력하기 위한 함수

 

 

문제풀이

1. N을 입력 받고, N*N크기의 인접 행렬을 기반으로 인접 리스트 edges를 초기화 해준다.
2. 관계를 체크하기 위해 N*N크기의 배열 relation을 초기화 해준다.
3. ans를 0으로 초기화 하고, 0~N번째 사람마다 bfs함수를 호출한다.
4. 정수형 큐 q를 초기화 하고, cnt를 0으로 초기화 해준다.
5. 현재 사람의 인접리스트를 순회하며 친구를 큐에 삽입, cnt를 증가, relation에 true로 변경하여 관계를 기록해준다.
6. 자기 자신을 true로 변경하되 cnt를 증가시키지 않는다.
7. q가 빌때까지 while루프를 순회하며 매 루프마다 요소를 한개씩 꺼내어 준다.
8. 내 친구의 친구가 이미 나와 관계가 없다면 관계를 true로 체크해 주고 cnt를 증가시켜 준다.
9. 루프가 종료된 후 cnt에 저장된 값을 리턴해 주고, ans와 비교하여 더 큰 값을 ans로 저장해 준다.
10. 모든 사람으로 부터 bfs함수를 수행이 완료되었다면 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

1. depth가 최대 2이므로 bfs내에서 친구의 친구를 찾은 후 큐에 친구의 친구를 삽입하지 않아야 한다.

 

정답 코드

import java.util.*;
import java.io.*;

public class Main {
    static List<List<Integer>> edges = new ArrayList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int bfs(int sn, boolean[][] relation) /*throws IOException*/ {
        Queue<Integer> q = new ArrayDeque<>();
        int cnt = 0;
        for (Integer i : edges.get(sn)) {
            q.add(i);
            relation[sn][i] = true;
            cnt++;

//            bw.write("현재 노드 : " + sn + "와 노드 " + i + "연결\n");
        }
        relation[sn][sn] = true;

        while (!q.isEmpty()) {
            int cn = q.poll();
            for (int nn : edges.get(cn)) {
                if (relation[sn][nn]) continue;
                relation[sn][nn] = true;
                cnt++;
//                bw.write("현재 노드 : " + sn + "와 노드 " + nn + "연결\n");
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; ++i) {
            edges.add(new ArrayList<>());
            st = new StringTokenizer(br.readLine());
            String a = st.nextToken();
            for (int j = 0; j < N; ++j) {
                if (a.charAt(j) == 'Y') {
                    edges.get(i).add(j);
                }
            }
        }

        boolean[][] relation = new boolean[N][N];
        int ans = 0;
        for (int i = 0; i < N; ++i) {
            ans = Math.max(ans, bfs(i, relation));
        }

        bw.write(ans + "\n");
        br.close();
        bw.close();
    }
}