백준 5567번 : 결혼식

 문제

www.acmicpc.net/problem/5567

5567번: 결혼식

5567 결혼식

 

 구현 방법

 bfs를 사용하여 구현하였습니다.

인접리스트를 생성하여 친구관계를 만들어주고 결혼식에는 친구와 친구의 친구까지 올 수 있으므로 카운팅 값을 넣어주었습니다.

상근이는 학번이 1이기 때문에 1부터 시작하여 상근이의 카운트는 0, 상근이에서 퍼져가는 친구는 상근이 카운트+1 해서 1, 친구의 친구는 친구 카운트+1 해서 2로 만들어 주고 현재 카운트+1이 3보다 크면 bfs에 못넣게 조건을 넣어주었습니다.

 

아래 그림은 제가 문제를 풀면서 간단하게 동작하는 과정을 그려본 것이니 참고해주세요.

 

 

 구현 코드

package BOJ.Silver;

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

public class B5567_결혼식 {
	static List<List<friend>> list;
	static int cnt;
	static Queue<friend> q;
	static boolean[] visit;
	static class friend {
		int value, cnt;

		public friend(int value, int cnt) {
			super();
			this.value = value;
			this.cnt = cnt;
		}
	}
    
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		// 인접리스트 생성
		list = new ArrayList<>();
		for (int i=0;i<=N;i++) {
			list.add(new ArrayList<>());
		}
        // 인접리스트에 값 넣어주기
		for (int i=0;i<M;i++) { 
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			list.get(n1).add(new friend(n2, 0));
			list.get(n2).add(new friend(n1, 0));
		}
		// 입력완료
		visit = new boolean[M+1]; // 방문체크 해줄 boolean 배열 선언
		q = new LinkedList<>();
		q.offer(new friend(1, cnt));
		visit[1] = true; 
		bfs();
		System.out.println(cnt);
	}
	
	static void bfs() {
		while(!q.isEmpty()) {
			friend now = q.poll();
			int size = list.get(now.value).size();
			for (int i=0;i<size;i++) {
				int value = list.get(now.value).get(i).value;
				if (!visit[value] && now.cnt+1<3) { // 현재 카운트+1이 3보다 작아야 들어갈 수 있음
					visit[value] = true;
					cnt++;
					q.offer(new friend(value, now.cnt+1));
				}
			}
		}
	}
}

 

정답!