링크 → https://www.acmicpc.net/problem/5567

• 아영

  • 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.StringTokenizer;
  
  public class boj5567 {
      static int N,M,cnt;
      static boolean[] checked;
      static boolean[][] relation;
      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());
          cnt = 0;
          checked = new boolean[N+1];
          relation = new boolean[N+1][N+1];
          StringTokenizer st;
          for (int i = 0; i < M; i++) {
              st = new StringTokenizer(br.readLine());
              int a = Integer.parseInt(st.nextToken());
              int b = Integer.parseInt(st.nextToken());
  
              relation[a][b]= true;
              relation[b][a] = true;
          }
          checked[1] = true;
          dfs(0,1);
          System.out.println(cnt);
      }
      private static void dfs(int depth,int now){
          if(depth==2){
              return;
          }
          for (int i = 1; i <= N; i++) {
              if(!relation[now][i]) continue;
              if(!checked[i]){
                  cnt+=1;
              }
              checked[i] = true;
              dfs(depth+1,i);
          }
      }
  }
  

  • 시간,메모리

  

• 은영

  • 코드

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.StringTokenizer;
  
  public class Main {
  
  	static int N,M,answer=0;
  	static int map[][];
  	static boolean[] visit;
  	public static void main(String[] args) throws NumberFormatException, IOException {
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer st;
  		
  		N = Integer.parseInt(br.readLine());
  		M = Integer.parseInt(br.readLine());
  		
  		map = new int[N+1][N+1];
  		visit = new boolean[N+1];
  		for (int i = 0; i < M; i++) {
  			st = new StringTokenizer(br.readLine()+" ");
  			int a = Integer.parseInt(st.nextToken());
  			int b = Integer.parseInt(st.nextToken());
  			
  			map[a][b] = 1;
  			map[b][a] = 1;
  		}
  		
  		bfs();
  		System.out.println(answer);
  	}
  	private static void bfs() {
  		visit[1] = true;
  		Queue<Point> q= new LinkedList<Point>();
  		q.add(new Point(1, 0));
  		while(!q.isEmpty()) {
  			Point temp = q.poll();
  			for (int j = 1; j <=N; j++) {
  				if(map[temp.x][j]==1&&!visit[j]&& temp.y<2) {
  					visit[j] = true;
  					answer++;
  					q.offer(new Point(j,temp.y+1));
  				}
  			}
  		}
  		
  	}
  }
  class Point{
  	int x;
  	int y;
  	public Point(int x, int y) {
  		this.x = x;
  		this.y = y;
  	}
  	
  }
  

  • 시간,메모리

  

• 건

  • 코드

  package day_0614;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;
  import java.util.Set;
  import java.util.StringTokenizer;
  
  public class BOJ5567 {
  
  	static int n, m;
  	static int answer;
  	static List<Set<Integer>> map;
  	
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer stk;
  		
  		n = Integer.parseInt(br.readLine());
  		m = Integer.parseInt(br.readLine());
  		
  		map = new ArrayList<>();
  		for (int i = 0; i <= n; i++) {
  			map.add(new HashSet<>());
  		}
  		
  		int input1, input2;
  		for (int i = 0; i < m; i++) {
  			stk = new StringTokenizer(br.readLine());
  			input1 = Integer.parseInt(stk.nextToken());
  			input2 = Integer.parseInt(stk.nextToken());
  			map.get(input1).add(input2);
  			map.get(input2).add(input1);
  		}
  		
  		bfs();
  		
  		System.out.println(answer);
  	}
  	
  	static void bfs() {
  		boolean[] visit = new boolean[n+1];
  		Queue<Integer> q = new LinkedList<>();
  		q.add(1);
  		visit[1] = true;
  		int now, count = 0, depth = 0;
  		while(!q.isEmpty()) {
  			depth = q.size();
  			for (int i = 0; i < depth; i++) {
  				now = q.poll();
  				Iterator<Integer> iter = map.get(now).iterator();
  				while(iter.hasNext()) {
  					int tNow = iter.next();
  					if (!visit[tNow]) {
  						count++;
  						visit[tNow] = true;
  						q.add(tNow);
  					}
  				}
  			}
  			depth++;
  			if (depth == 3) {
  				break;
  			}
  		}
  		answer = count;
  	}
  }
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ5567 {
      
      private var N = 0
      private var answer = 0
      private var points: [[Int]] = []
      private var visited: [Bool] = []
      
      func solve() {
          readComponents()
          calc()
          printAnswer()
      }
      
      private func readComponents() {
          self.N = Int(readLine()!)!
          let M = Int(readLine()!)!
          
          points = .init(repeating: [], count: N + 1)
          visited = .init(repeating: false, count: N + 1)
          
          for _ in 0..<M {
              let temp = readLine()!.split(separator: " ").map { Int($0)! }
              points[temp[0]].append(temp[1])
              points[temp[1]].append(temp[0])
          }
      }
      
      private func calc() {
          var queue: [(value: Int, depth: Int)] = []
          
          queue.append((1, 0))
          visited[1] = true
          
          while !queue.isEmpty {
              let now = queue.remove(at: 0)
              
              if now.depth == 2 { break }
              
              for value in points[now.value] {
                  if visited[value] { continue }
                  visited[value] = true
                  queue.append((value, now.depth + 1))
                  answer += 1
              }
          }
      }
      
      private func printAnswer() {
          print(answer)
      }
  }
  
  BJ5567().solve()
  

  • 시간,메모리