1238. [S/W 문제해결 기본] 10일차 - Contact

LEVEL D4

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE

SW Expert Academy

 

BFS 기본문제 유형이다.

 

소스보기

 

#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
int map[101][101];
int visited[101];
int N, start, maxVal;
int bfs()
{
	int lastNum;
	queue<int> que;
	que.push(start);
	visited[start] = 1;
	while (!que.empty()) {
		int queSize = que.size();
		lastNum = 0;
		for (int i = 0; i < queSize; i++) {
			int n = que.front(); que.pop();
			if (lastNum < n) {
				lastNum = n;
			}
			for (int j = 1; j <= maxVal; j++) {
				if (map[n][j] && visited[j] == 0) {
					que.push(j);
					visited[j] = 1;
				}
			}
		}
	}
	return lastNum;
}
int main()
{
	int tc = 1;
	for (; tc <= 10; tc++) {
		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));
		maxVal = 0;
		scanf("%d %d", &N, &start);
		for (int i = 0; i < N / 2; i++) {
			int from, to;
			scanf("%d %d", &from, &to);
			map[from][to] = 1;
			if (maxVal < from) {
				maxVal = from;
			}
			if (maxVal < to) {
				maxVal = to;
			}
		}
		printf("#%d %d\n",tc, bfs());
	}
}