문제 링크

처음 접근했을 때

• bfs(int idx, int depth)로 한번만 main 메소드에서 실행시켜서 depth가 2를 초과되면 return하게 해야하나?라는 생각이 들어 그렇게 구현했는데
  • 언제 return해야되는지... 이게 한번만 쭉 갔다가 되돌아오면 되는 게 아니라 depth가 2이하인 모든 곳을 방문해야하는데 그걸 구현하는 부분에서 막혔다.
• 일단 보자마자 BOJ 1260번 떠올라서 그거 코드를 생각하고 ArrayList<ArrayList<Integer>>로 구현한 건 잘했다...

잘못 판단한 부분

일단 너무 많은 걸 잘못했는데 ^^..

• 처음에 visited가 필요없을 거라고 생각했다. 왜지? 좀더 침착히 설계하도록.....
• 아래를 arr.add가 아니라 매번 선언하고 있었다... (arr = new ArrayList<>(); -> 뭐하세요?)

for (int i = 0; i <= n; i++)
   arr.add(new ArrayList<>());

• bfs(idx, depth)가 아니라 bfs 안에서 depth는 따로 처리하면 된다.
• if (dep == 2) continue; 이 부분을 어디서 끊어줘야될지 헷갈렸다..
  • 결론적으로는 for문 전에 왜냐면 dep가 2면 더 들어가면 안되니까.. q.add()쪽을 못 가게 해야되니까..
• result++; 이것도 어디서 해야될지 고민됐다..
  • 일단 저기까지 왔다는 거는 dep이 2 미만이라는 것. 2라면 그 전에 continue 처리됐을 꺼니까
  • 그래서 방문하지 않았다면 방문 처리해주고 result++로 결혼식에 와라! 처리해주고 q.add() 처리해서 그 다음 친구도 볼 수 있게 하면 된다.
• for문의 역할 for (int next : arr.get(cur))
  • 지정된 cur과 연결된 친구를 끝까지 보는 역할 (dep는 계속 체크해주니까 안심하고..)

정답 코드

package algo.ct.M12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_5567_결혼식_S2 {
    static int n, m;
    static ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
    static int result = 0;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 동기 수
        m = Integer.parseInt(br.readLine()); // 리스트 길이

        for (int i = 0; i <= n; i++)
            arr.add(new ArrayList<>());
        visited = new boolean[n+1];

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            arr.get(a).add(b);
            arr.get(b).add(a);
        }

        bfs(1);
        System.out.println(result);
    }

    public static void bfs(int idx) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{idx, 0});
        visited[idx] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int cur = now[0];
            int dep = now[1];

            if (dep == 2) continue;

            for (int next : arr.get(cur)) {
                if (!visited[next]) {
                    visited[next] = true;
                    result++;
                    q.add(new int[]{next, dep + 1});
                }
            }
        }
    }
}