[백준] 5567: 결혼식 (JAVA)

5567: 결혼식 (실버2)

 

ArrayList<Integer>[]

이런 문제를 풀때 나는 ArrayList<Integer>[] 처럼 ArrayList 내에 배열을 넣어서 푸는걸 좋아한다.

오랜만에 풀었더니 또 정의하는 법 까먹었다 .. 앞으론 진짜 안까먹어야지

ArrayList<Integer>[] list = new ArrayList<>();

list = new ArrayList[N];

for(int i=0; i<N; i++){
	list[i] = new ArrayList<>();
}

list[0].add(1);
list[0].get(0); //1

풀이

상근이의 친구의 친구 까지만 결혼식에 초대한다. 즉, depth가 2인 친구들까지만 초대한다는 뜻이다.

이 경우 bfs와 dfs 둘 다로 문제를 해결할 수 있다. 난 bfs로 문제를 풀었다.

 

위의 ArrayList<Integer>[] 를 사용하면, 

6
5
1 2
1 3
3 4
2 3
4 5

이런 형태의 입력이 주어졌을 때

1 - 2, 3
2 - 1, 3
3 - 1, 4
4 - 3, 5
5 - 4

이런 형태로 저장되게 된다.

즉, 누가 누구와 친구인지 더 명확해지고 NxN 배열에 넣었을 때보다 방문해야하는 범위가 줄어들기 때문에 더 효율적이다.

static void bfs(int idx, int cnt) {
	Queue<Node> q = new LinkedList<>();
	q.offer(new Node(idx, cnt));
	visited[idx] = true;
		
	while(!q.isEmpty()) {
		Node n = q.poll();
		
		if(n.count == 2) {
			break;
		}
			
		for(int i=0; i<friendship[n.now].size(); i++) {
			int newIdx = friendship[n.now].get(i);
			if(!visited[newIdx]) {
				q.offer(new Node(newIdx, n.count+1));
				visited[newIdx] = true;
			}
		}
	}
}

나는 bfs를 돌면서 상근이의 친구의 친구까지 visited배열에 방문처리를 해주고 break 문으로 빠져나오는 코드를 작성했다.

visited 배열에서 true로 방문한 숫자의 친구만 결혼식에 부르면 된다.

전체코드

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

public class 실버2_5567_결혼식 {
	static class Node{
		int now;
		int count;
		Node(int now, int count){
			this.now = now;
			this.count = count;
		}
	}
	static int n;
	static int m;
	static ArrayList<Integer>[] friendship;
	static boolean visited[];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		
		friendship = new ArrayList[n+1];
		visited = new boolean[n+1];
		for(int i=0; i<n+1; i++) {
			friendship[i] = new ArrayList<>();
		}
				
		int tmp = 0;
		for(int i=0; i<m; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int friend1 = Integer.parseInt(st.nextToken());
			int friend2 = Integer.parseInt(st.nextToken());
			
			friendship[friend1].add(friend2);
			friendship[friend2].add(friend1);
		}
		
		bfs(1, 0);
		
		int answer = 0;
		for(int i=2; i<n+1; i++) {
			if(visited[i]) {
				answer++;
			}
		}
		
		System.out.println(answer);
		
		
	}
	static void bfs(int idx, int cnt) {
		Queue<Node> q = new LinkedList<>();
		q.offer(new Node(idx, cnt));
		visited[idx] = true;
		
		while(!q.isEmpty()) {
			Node n = q.poll();
			
			if(n.count == 2) {
				break;
			}
			
			for(int i=0; i<friendship[n.now].size(); i++) {
				int newIdx = friendship[n.now].get(i);
				if(!visited[newIdx]) {
					q.offer(new Node(newIdx, n.count+1));
					visited[newIdx] = true;
				}
			}
		}
	}
}