11. 아는 사람(중)

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Java 8 2.0s
Python 2.0s
Memory limit: 64M
Java 8 128M
Python 128M
Author:
jtpark
Problem type

네모바지 스폰지밥의 '캠핑은 즐거워'편을 보면 다음과 같은 대사가 나온다.

스폰지밥: 뚱이 말이 맞아. 바다곰을 우습게 보지 말라구. 내가 어떤 남자를 만났는데, 그 사람의 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 또 아는 사람의 그 사람의 또 아는 사람의 옆집 사람의 또 아는 사람의 또 아는 사람의...

이를 듣고 있던 징징이는 심기가 매우 불편하다. 왜냐하면 스폰지밥이 불필요하게 많이 "아는 사람의 "를 외친다고 생각했기 때문이다.

스폰지밥이 최소의 횟수만큼 "아는 사람의 "를 외칠 수 있도록 도와주자.

　

\(N\)명의 사람에 대한 아는 사람 관계가 주어질 때, 사람 \(p\)가 최소 몇 번의 아는 사람 관계를 거쳐야 사람 \(q\)에 도달할 수 있는지 알아내는 프로그램을 작성하시오.

입력

  • 첫째 줄에 사람의 수 \(N\), 아는 사람 관계의 수 \(M\)이 주어진다.\((2 ≤ N ≤ 2000, 1 ≤ M ≤ 10000)\)
  • 그 다음 줄부터 \(M\)개의 줄에 \(a, b\)가 주어진다. 이는 \(a\)와 \(b\)가 서로 아는 사람이라는 뜻이다.\((1 ≤ a ≤ N, 1 ≤ b ≤ N, a ≠ b)\)
  • 그 다음 줄에 \(p\)와 \(q\)가 주어진다.\((1 ≤ p ≤ N, 1 ≤ q ≤ N, p ≠ q)\)

출력

  • \(p\)와 \(q\)가 아무런 관계가 없는 경우, "모르는 사람"을 출력한다.
  • \(p\)에서 \(q\)까지 도달하기 위해 최소 \(n\)번의 아는 사람 관계를 거쳐야 하는 경우 \(n-1\)번의 "아는 사람의 "를 출력하고 나서 "아는 사람"을 출력한다.

입력 예시 1

4 3
1 2
1 3
3 4
3 1

출력 예시 1

아는 사람

입력 예시 2

4 3
1 2
1 3
3 4
2 4

출력 예시 2

아는 사람의 아는 사람의 아는 사람

입력 예시 3

4 2
1 2
3 4
1 4

출력 예시 3

모르는 사람

입력 예시 4

7 8
1 2
1 3
1 4
2 5
3 6
4 7
5 6
6 7
1 6

출력 예시 4

아는 사람의 아는 사람

예시 4 힌트

힌트

  • Java의 경우 BufferedWriter를 사용하여 유니코드를 출력할 수 있다. 다른 언어는 기본 입출력 그대로 사용해도 된다.
  • 이 문제는 가중치가 없는 그래프의 최단 경로를 구하는 문제로서, DFS를 사용할 수 없는 문제이다. 기존에 구현했던 간단한 BFS에서 depth별로 구분하는 과정만 추가하면 된다.

Comments


  • 0
    S20174242  commented on Nov. 19, 2020, 5:41 p.m.

    https://velog.io/@skyepodium/BFS%EB%8A%94-%EB%82%AF%EC%84%A4%EC%96%B4%EC%84%9C 블로그에 문제관련 설명이 잘되어있습니다.


  • 0
    S20174242  commented on Nov. 15, 2020, 5:21 p.m.

    컴파일러가 한글을 인식못하는거같습니다 테스트 케이스가 전부 ???? 로만 출력됩니다


    • 0
      jtpark  commented on Nov. 15, 2020, 5:35 p.m. ← edit 3

      자바의 System.out.print의 유니코드 인코딩 방식이 다른 것 같으니 BufferedWriter를 사용해 보세요.

      import java.io.*;
...
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write("모르는 사람");
...
bw.flush(); // 마지막에 한 번만 호출