지구정복

[BFS,DFS] 백준 - 바이러스 본문

데이터 엔지니어링 정복/Algorithm

[BFS,DFS] 백준 - 바이러스

eeaarrtthh 2021. 6. 25. 15:29
728x90
반응형

-자바 bfs

package bfs_dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Virus1 {
	public static int[][] arr;
	public static boolean[] visit;
	public static int sum = 0;
	
	private static void bfs( int start ) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add( start );
		visit[start] = true;
		
		while( !q.isEmpty() ) {
			int temp = q.peek();
			q.poll();
			
			for( int i=1; i<arr.length; i++ ) {
				if( arr[temp][i] == 1 && visit[i] == false ) {
					q.add(i);
					visit[i] = true;
					sum += 1;
				}
			}
			System.out.println( "temp는 ? " + temp );
		}
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		
		int n = Integer.parseInt( br.readLine() );
		int m = Integer.parseInt( br.readLine() );
		
		arr = new int[n+1][n+1];
		visit = new boolean[n+1];
		
		for( int i=1; i<=m; i++ ) {
			st = new StringTokenizer( br.readLine() );
			int a = Integer.parseInt( st.nextToken() );
			int b = Integer.parseInt( st.nextToken() );
			
			arr[a][b] = 1;
			arr[b][a] = 1;
		}
			
//		for( int i=0; i<arr.length; i++ ) {
//			for( int j=1; j<arr.length; j++ ) {
//				System.out.print( arr[i][j] );
//			}
//			System.out.println( );
//		}
		
		bfs( 1 );
		System.out.println( sum );
	}

}

 

-자바dfs

package bfs_dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ2606 {
    static int n, m, res;
    static int[][] net;
    static boolean[] visit;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt( br.readLine() );
        m = Integer.parseInt( br.readLine() );

        net = new int[n+1][n+1];
        visit = new boolean[n+1];

        StringTokenizer st;
        for( int i=0; i<m; i++ ) {
            st = new StringTokenizer( br.readLine() );
            int a = Integer.parseInt( st.nextToken() );
            int b = Integer.parseInt( st.nextToken() );

            net[a][b] = net[b][a] = 1;
        }

        dfs( 1 );
        System.out.println( --res );
    }

    static void dfs( int start ) {
        visit[start] = true;
        res++;

        for( int i=1; i<=n; i++ ) {
            if( net[start][i] == 1 && visit[i] == false ) {
                dfs( i );
            }
        }
    }
}

 

-파이썬 dfs

from sys import stdin
input = stdin.readline
n = int( input() )
m = int( input() )
net = [ [0]*(n+1) for _ in range(n+1) ]

for _ in range( m ):
    a, b = map( int, input().split() )
    net[a][b] = net[b][a] = 1

res = 0
visit = [False]*(n+1)

def dfs(start):
    global res, n
    visit[start] = True
    res += 1

    for i in range(1, n+1):
        if net[start][i] == 1 and visit[i] == False:
            dfs( i )

dfs( 1 )

print( res-1 )
728x90
반응형
Comments