백준 - 케빈 베이컨의 6단계 법칙

문제 링크입니다 : www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

 

 

bfs 구현 문제였다. 난이도는 매우 쉬움

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

int N, M;
vector<vector<int>> adj;
vector<bool> visited;

int dfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    int ret = 0;
    int dist = 1;
    while(!q.empty()) {
        int qSize = q.size();
        for(int i = 0; i < qSize; i++) {
            int cur = q.front();
            q.pop();

            for(int j = 0; j < adj[cur].size(); j++) {
                int next = adj[cur][j];
                if(visited[next]) continue;
                visited[next] = true;
                q.push(next);
                ret += dist;
            }
        }
        dist++;
    }

    return ret;
}


int main() {
    cin >> N >> M;
    adj.assign(N + 1, vector<int>());

    int u, v;
    for(int i = 0; i < M; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int minVal = INF;
    int minNum = 0;

    for(int i = 1; i <= N; i++) {
        visited.assign(N + 1, false);
        int num = dfs(i);
        if(num < minVal) {
            minVal = num;
            minNum = i;
        }
    }

    cout << minNum;


    return 0;
}

 

 

from collections import deque

N, M = map(int, input().split())

adj = [[] for _ in range(N + 1)]
visited = []


def dfs(start: int) -> int:
    global visited
    global adj
    q = deque()
    q.append(start)
    visited[start] = True

    ret = 0
    dist = 0
    while len(q) != 0:
        dist += 1
        q_size = len(q)
        for i in range(q_size):
            cur = q.popleft()
            for j, n in enumerate(adj[cur]):
                if visited[n]: continue
                visited[n] = True
                ret += dist
                q.append(n)

    return ret




for i in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)


min_val = float('inf')
min_index = 0
for i in range(1, N + 1):
    visited = [False] * (N + 1)
    num = dfs(i)
    if num < min_val:
        min_val = num
        min_index = i

print(min_index)

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	static int N, M;
	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();;
	static ArrayList<Boolean> visited = new ArrayList<Boolean>();
	
	static void setVisitedFalse() {
		visited.clear();
		for(int i = 0; i <= N; i++) {
			visited.add(false);
		}
	}
	
	static int dfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		visited.set(start, true);
		
		int ret = 0;
		int dist = 0;
		
		while(!q.isEmpty()) {
			dist++;
			int qSize = q.size();
			for(int i = 0; i < qSize; i++) {
				int cur = q.poll();
				
				for(int j = 0; j < adj.get(cur).size(); j++) {
					int next = adj.get(cur).get(j);
					if(visited.get(next)) continue;
					visited.set(next, true);
					ret += dist;
					q.add(next);
				}
				
			}
		}
		
		return ret;
	}
	

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		
		for(int i = 0; i <= N; i++) {
			adj.add(new ArrayList<Integer>());
		}
		
		int u, v;
		for(int i = 0; i < M; i++) {
			u = sc.nextInt();
			v = sc.nextInt();
			
			adj.get(u).add(v);
			adj.get(v).add(u);
		}
		
		int minVal = Integer.MAX_VALUE;
		int minIndex = 0;
		
		for(int i = 1; i <= N; i++) {
			setVisitedFalse();
			int num =  dfs(i);
			if(num < minVal) {
				minVal = num;
				minIndex = i;
			}
		}
		
		
		System.out.println(minIndex);
		

		bw.flush();
		bw.close();
		
		
		br.close();
    }
}

 

 

개발 환경 : vscode, eclipse 2020-03, C++ 11, Python3, Java 11

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~