[코딩테스트] 친구인가?👯‍♀️(BFS)

최지나·2024년 3월 26일

Java

코딩테스트

목록 보기

134/154

문제

오늘은 새 학기 새로운 반에서 처음 시작하는 날이다. 현수네 반 학생은 N명이다. 현수는 각 학생들의 친구관계를 알고 싶다.

모든 학생은 1부터 N까지 번호가 부여되어 있고, 현수에게는 각각 두 명의 학생은 친구 관계가 번호로 표현된 숫자쌍이 주어진다.

만약 (1, 2), (2, 3), (3, 4)의 숫자쌍이 주어지면 1번 학생과 2번 학생이 친구이고, 2번 학생과 3번 학생이 친구, 3번 학생과 4번 학생이 친구이다.

그리고 1번 학생과 4번 학생은 2번과 3번을 통해서 친구관계가 된다.
학생의 친구관계를 나타내는 숫자쌍이 주어지면 특정 두 명이 친구인지를 판별하는 프로그램을 작성하세요.

두 학생이 친구이면 “YES"이고, 아니면 ”NO"를 출력한다.

입력

첫 번째 줄에 반 학생수인 자연수 N(1<=N<=1,000)과 숫자쌍의 개수인 M(1<=M<=3,000)이 주어지고,
다음 M개의 줄에 걸쳐 숫자쌍이 주어진다.
마지막 줄에는 두 학생이 친구인지 확인하는 숫자쌍이 주어진다.

출력

첫 번째 줄에 “YES"또는 "NO"를 출력한다.

예시 입력 1

예시 출력 1

NO

생각

1) 친구 관계 설정

1번 친구가 2번이면, 2번 친구도 1번이므로 양방향으로 생각해주어야 한다
친구들간의 양방향 관계를 연결 리스트에 담아 보자

2) 두 사람이 친구?

BFS를 사용하여 가장 가까운 친구 관계부터 (친구의 친구보다는 친구가 가깝다고 생각) 탐색해보자.
둘 중 한 사람(s1)을 시작접으로 잡고, 시작 점의 친구들부터 큐에 넣어가면서 탐색
이미 친구관계인거 확인한 사람 또 확인 안하도록 visited 배열 사용
큐가 빌 때까지 다른 한 사람(s2)과의 친구관계가 나오지 않으면 "NO" 나오면 "YES" 리턴

코드


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class IsFriend {

    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] visited;

    public String areTheyFriends(int s1, int s2) {
        Queue<Integer> Q = new LinkedList<>();
        visited[s1] = 1;
        for (int g : graph.get(s1)) {
            Q.offer(g);
        }
        while (!Q.isEmpty()) {
            int cur = Q.poll();
            for (int g : graph.get(cur)) {
                if (visited[g] == 0) {
                    if (g == s2)
                        return "YES";
                    Q.offer(g);
                    visited[g] = 1;
                }
            }
        }
        return "NO";
    }

    public static void main(String[] args) {
        IsFriend T = new IsFriend();
        Scanner kb = new Scanner(System.in);

        int N = kb.nextInt();
        int M = kb.nextInt();
        visited = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < M; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        int s1 = kb.nextInt();
        int s2 = kb.nextInt();

        System.out.println(T.areTheyFriends(s1, s2));

        kb.close();
    }

}