[백준 - Java] 5567번 : 결혼식

문제

www.acmicpc.net/problem/5567

5567번: 결혼식

설명

ai와 bi가 친구라면, bi와 ai도 친구관계이기에 양방향 그래프로 만들었다.

그리고 친구관계를 인접 리스트를 이용해 표현했다.

 

상근이는 1번이고, 1번과 인접한 정점(친구). 1번과 인접한 정점의 인접한 정점(친구의 친구)

딱 3번을 거친, 3번까지 BFS 탐색한 정점까지만 결혼식에 초대할 수 있다는 것.

 

정점의 방문여부를 확인하는 visited배열은 기존에 작성할 때 boolean으로 주로 선언했다. (T/F만 보면 되니까)

하지만 여기선 3번을 거쳤다는 것을 확인하기 위해 int값으로 선언했다.

방문하지 않은 인접한 정점들을 for문을 통해 찾을 때마다 visited배열의 값을 +1 해줌으로써 bfs 탐색이 어느 정도 깊이 들어갔나 확인한다.

그리고 visited배열의 값이 3인 정점에 도달했다면, 1번의 친구와 친구의 친구까지 다 확인한 것임으로 bfs를 끝내준다.

 

전체 코드

import java.util.*;

public class Main {
	public static ArrayList<Integer>[] adjList;
	public static int[] visited;
	public static int ans = 0;


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		adjList = new ArrayList[N + 1];
		visited = new int[N + 1];

		for(int i = 1; i <= N; i++) {
			adjList[i] = new ArrayList<Integer>();
		}

		for(int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			adjList[a].add(b);
			adjList[b].add(a);
		}

		bfs();
		
		System.out.println(ans);
	}

	public static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(1);
		visited[1]++;

		while(!queue.isEmpty()) {
			int v = queue.poll();

			// 친구의 친구까지 확인 완료 
			if(visited[v] >= 3) {
				break;
			}

			for(int next : adjList[v]) {
				if(visited[next] == 0) {
					visited[next] = visited[v] + 1;
					queue.add(next);
					ans++;
				}
			}
		}
	}
}

 

GITHUB

KwonMinha/BOJ