이를 정점 1을 시작으로 너비우선탐색(BFS)을 했을 경우 여러가지가 가능하지만 가능한 경우의 한 가지는
1 2 4 6 3 5 이다.
따라서 하나의 결과를 위해 다음과 같은 제약조건을 적용한다.
1. 정점 1부터 방문한다.
2. 한 정점에서 갈 수 있는 곳이 여러개 있을 경우 먼저 입력된 정점부터 방문한다.
3. 어떤 정점과 연결되지 않은 경우는 번호가 빠른 순으로 방문한다.
주어진 그래프는 양방향 무가중치 그래프이다.
1392: [자료구조] 너비우선탐색(BFS)
메모리：128 MB
시간：1.000 S
표준 입력 및 출력
문제유형
채점방법：일반
만든사람：
제출：0
통과：0
문제설명
너비우선탐색(BFS)는 그래프의 임의의 한 정점에서 출발하여, 연결된 정점들 중 하나에 대해서 너비 순으로 먼저 탐색해 나가는 탐색법이다. 예를 들어 다음과 같은 그래프를 보자.
이를 정점 1을 시작으로 너비우선탐색(BFS)을 했을 경우 여러가지가 가능하지만 가능한 경우의 한 가지는
1 2 4 6 3 5 이다.
따라서 하나의 결과를 위해 다음과 같은 제약조건을 적용한다.
1. 정점 1부터 방문한다.
2. 한 정점에서 갈 수 있는 곳이 여러개 있을 경우 먼저 입력된 정점부터 방문한다.
3. 어떤 정점과 연결되지 않은 경우는 번호가 빠른 순으로 방문한다.
주어진 그래프는 양방향 무가중치 그래프이다.
이를 정점 1을 시작으로 너비우선탐색(BFS)을 했을 경우 여러가지가 가능하지만 가능한 경우의 한 가지는
1 2 4 6 3 5 이다.
따라서 하나의 결과를 위해 다음과 같은 제약조건을 적용한다.
1. 정점 1부터 방문한다.
2. 한 정점에서 갈 수 있는 곳이 여러개 있을 경우 먼저 입력된 정점부터 방문한다.
3. 어떤 정점과 연결되지 않은 경우는 번호가 빠른 순으로 방문한다.
주어진 그래프는 양방향 무가중치 그래프이다.
입력조건
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력조건
BFS결과를 출력하라.
입력예시 복사
7
6
1 2
2 3
1 5
5 2
5 6
4 7출력예시 복사
1 2 5 3 6 4 7