[BOJ/백준] 5567 결혼식 (S2)

2024. 7. 5. 19:33· Algorithm PS/Baekjoon Online Judge
목차
  1. 문제
  2. 풀이
  3. Code

문제

https://www.acmicpc.net/problem/5567

풀이

Code

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int N, M;
    static int[] distance;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        distance = new int[N + 1];  // 거리
        Arrays.fill(distance, -1);  // -1로 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a_i = Integer.parseInt(st.nextToken());
            int b_i = Integer.parseInt(st.nextToken());
            graph[a_i].add(b_i);  // 무방향 그래프이므로 양방향 그래프로 설정해줘야 함.
            graph[b_i].add(a_i);
        }

        int cnt = bfs(1);
        bw.write(cnt + "");
        bw.flush();
        bw.close();
    }
    private static int bfs(int start) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);  // 상근이의 위치는 항상 1
        distance[start] = 0;  // 거리는 0
        int cnt = 0;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (distance[now] >= 1 && distance[now] <= 2) cnt++;  // 1인 경우는 친구인 경우이고, 2인 경우는 친구의 친구인 경우.

            for (int next : graph[now]) {
                if (distance[next] != -1) continue;  // 다음 노드가 이미 방문한 헛간이면 pass
                queue.add(next);
                distance[next] = distance[now] + 1;
            }
        }

        return cnt;
    }
}

728x90

'Algorithm PS > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ/백준] 6118 숨바꼭질 (S1)  (2) 2024.07.08
[BOJ/백준] 2260 회장뽑기 (G5)  (0) 2024.07.06
[BOJ/백준] 11726 2×n 타일링 (S3)  (0) 2024.07.03
[BOJ/백준] 1788 피보나치 수의 확장 (S3)  (0) 2024.07.03
[BOJ/백준] 9251 LCS (G5)  (0) 2024.05.23
  1. 문제
  2. 풀이
  3. Code
'Algorithm PS/Baekjoon Online Judge' 카테고리의 다른 글
  • [BOJ/백준] 6118 숨바꼭질 (S1)
  • [BOJ/백준] 2260 회장뽑기 (G5)
  • [BOJ/백준] 11726 2×n 타일링 (S3)
  • [BOJ/백준] 1788 피보나치 수의 확장 (S3)
kyung.Kh
kyung.Kh
kyung.Kh
Dev..studynote
kyung.Kh
전체
오늘
어제
05-19 22:45
  • 분류 전체보기 (68)
    • Algorithm PS (29)
      • Baekjoon Online Judge (29)
      • Programmers (0)
    • Computer Science (4)
      • Databse (0)
      • Operating System (0)
      • Computer Network (0)
      • Computer Architecture (0)
      • Algorithm (4)
    • Spring (29)
      • Spring Boot (1)
      • 스프링 핵심 원리 - 기본편(인프런 김영한) (7)
      • Java (1)
      • 자바 ORM 표준 JPA 프로그래밍 (20)
    • Project (2)
      • 문제 & 해결 (2)
    • Book (3)
      • 객체지향의 사실과 오해 (3)
    • 우하한테크코스 (1)
      • precourse (1)

최근 글

인기 글

블로그 메뉴

    태그

    • 구현
    • 인프런
    • 객체지향
    • 재귀
    • BFS
    • 스프링
    • springboot
    • dfs
    • Union-Find
    • Spring
    • 스프링 기본편
    • 그리디
    • 해시를 사용한 집합과 맵
    • 알고리즘
    • 스프링 김영한
    • 스프링부트
    • JPA
    • Graph
    • 백준
    • DP
    hELLO · Designed By 정상우.v4.2.2
    kyung.Kh
    [BOJ/백준] 5567 결혼식 (S2)
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.