백준_5567 결혼식(자바) / 구현

시간 & 메모리 제한

문제

입력 & 출력

구현을 이용한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Back_5567 {

	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());
		StringTokenizer st;
		//친구간의 관계 표시를 위한 배열
		boolean [][] arr = new boolean[N+1][N+1];
		//누가 오는 동기 인지 표시 하기 위한 배열
		boolean[] visited = new boolean[N+1];
		int ans=0;
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a][b] = true;
			arr[b][a] = true;
		}
		
		for (int i = 2; i <=N; i++) {
			//친구인 경우
			if(arr[1][i]== true) {
				if(!visited[i]) {
					ans ++;
					visited[i]=true;
				}
				
				// 친구의 친구인 경우 찾기
				for (int j = 2; j <=N; j++) {
					if(arr[i][j]==true && !visited[j]) {
						ans ++;
						visited[j]=true;
					}
				}
			}
		}
		System.out.println(ans);
	}

}

 

- 이 문제를 읽었을 때, 있는 그대로 풀면 될꺼 같다는 생각이 들었습니다.

 

- 물론 이 문제를 bfs로 풀 수 있다고 생각 했지만, 가장 먼저 든 생각으로 문제를 풀었습니다.

 

- for문을 통해서 1차적으로 나와 친구인 관계를 찾았고, 그 친구고 아직 방문하지 않은 친구이면, 방문 처리 및 카운트를 해줬습니다.

 

- 친구에 값을 아는 상태에서 친구의 친구를 찾기 위해서 for문을 한번 더 돌렸습니다.