백준 5567번
https://www.acmicpc.net/problem/5567

문제

---

생각하기

---

• 인접리스트와 인접행렬을 사용해 2가지 방법으로 풀 수 있다.
  • 인접리스트는 BFS탐색을 통해서 1을 통해 갈 수 있는 모든 노드를 탐색한다.
  • 인접행렬은 2차원 배열의 1행을 탐색해서 갈 수 있는 노드를 모두 찾아서 1로 치환을 해준다.

동작

			for (int friendNum : nodeList.get(num)) {
				if(dist[friendNum] == 0) {
					dist[friendNum] = dist[num] + 1;
					que.offer(friendNum);
				}
			}

방문한적이 없는 노드, 즉 dist의 값이 0일 경우, 기존의 dist의 값에서 + 1을 하여 새로 갱신해준다.
이렇게 하면 1번 노트에서 출발해서 갈 수 있는 노드를 모두 알 수 있다.

		for(int i=2; i<=N; i++) {
			if(arr[1][i] == 0) continue;
			dist[i] = 1;
			
			for(int j=2; j<=N; j++) {
				if(arr[i][j] == 1) {
					dist[i] = dist[j] = 1;
				}
			}
		}

인접행렬에서는 1행을 기준으로 갈 수 있는 곳을 찾는다. 1의 값을 가지고 있을 때는 연결된 노드를 의미한다.
또한 1을 가지고 있는 노드가 다른 노드를 가지고 있는지 체크한다. 체크하는 과정에서 또 1이 나올 경우, ㅏ친구의 친구이므로 정답으로 포함된다.

코드

---

Java

인접리스트

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

public class Main {
	static List<List<Integer>> nodeList;
	static int dist[];
	static boolean visit[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		nodeList = new ArrayList<>();
		for (int i = 0; i <= N; i++) {
			nodeList.add(new ArrayList<>());
		}
		dist = new int[N + 1];
		visit = new boolean[N + 1];

		while (M-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int parent = Integer.parseInt(st.nextToken());
			int son = Integer.parseInt(st.nextToken());

			nodeList.get(parent).add(son);
			nodeList.get(son).add(parent);
		}

		graphSearch(1);

		int resultCount = 0;
		for (int i = 2; i <= N; i++) {
			if (dist[i] <= 3 && dist[i] > 0) {
				resultCount++;
			}
		}

		System.out.print(resultCount);
	} // End of main

	private static void graphSearch(int startNum) {
		Queue<Integer> que = new LinkedList<>();
		que.offer(startNum);
		dist[startNum] = 1;

		while (!que.isEmpty()) {
			int num = que.poll();

			for (int friendNum : nodeList.get(num)) {
				if(dist[friendNum] == 0) {
					dist[friendNum] = dist[num] + 1;
					que.offer(friendNum);
				}
			}

		}

	} // End of graphSearch
} // End of Main class

인접행렬

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

public class Main {
	static int arr[][];
	static int dist[];
	static int N, M;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		
		arr = new int[N+1][N+1];
		dist = new int[N+1];
		while(M-->0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int parent = Integer.parseInt(st.nextToken());
			int son = Integer.parseInt(st.nextToken());
			
			arr[parent][son] = arr[son][parent] = 1;
		}
		
		for(int i=2; i<=N; i++) {
			if(arr[1][i] == 0) continue;
			dist[i] = 1;
			
			for(int j=2; j<=N; j++) {
				if(arr[i][j] == 1) {
					dist[i] = dist[j] = 1;
				}
			}
		}
		
		
		int resultCount = 0;
		for(int i=1; i<=N; i++) {
			resultCount += dist[i];
		}
		
		
		System.out.println(resultCount);
	} // End of main
} // End of Main class