[코테 매일 풀기 1일차] 1023

1. 백준 2606 바이러스

첫번째 아이디어
인접행렬로 자료구조를 나타내서 dfs로 호출한 개수를 센다.

package boj_silver.p2606_바이러스;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Review2 {

    static boolean[] visited; //방문한 노드를 체크한다. 
    static List<Integer>[] computers; //인접 리스트를 만들기 위한 자료구조이다. 
    static int cnt; //dfs 호출을 센다 

    public static void main(String[] args) {
    	//입력 받기 
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        
        //초기화 
        visited  = new boolean[N+1];
        computers = new ArrayList[N+1];
        //인접 리스트 초기화 
        for (int i = 1; i<=N; i++){
            computers[i] = new ArrayList<Integer>();
        }
        //연결 받기
        for (int i = 0; i<M; i++){
            int a =scan.nextInt();
            int b =scan.nextInt();
            computers[a].add(b);
            computers[b].add(a);
        }
        // 1번 정점으로부터 찾기 
        dfs(1);
        System.out.println(cnt-1);
    }
    //dfs 코드 
    static void dfs(int node){
        visited[node] = true;
        cnt ++;
        for (int x: computers[node]){
            if(!visited[x]){
                dfs(x);
            }
        }
    }
}

두번째 아이디어
union, find 를 사용해 같은 집합인 개수 세기

package boj_silver.p2606_바이러스;

import java.util.Scanner;

public class Review2_union {

    static int[] computers; //부모 노드 저장할 배열 선언 
    
    public static void main(String[] args) {
    	//입력 받기 
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();

        computers = new int[n+1];
        
        //부모 노드 초기화: 자기 자신이 부모 노드 
        for (int i = 1; i <= n; i++) {
            computers[i] = i; 
        }
        //입력 받기 
        for (int i = 0; i< m; i++){
            int a = scan.nextInt();
            int b = scan.nextInt();
            union(a, b);
        }
        //1번 노드와 같은 집합인지 확인 -> cnt++ 
        int cnt = 0;
        for (int i = 2; i <= n; i++){ //2번부터 시작
            if(find(i) == find(1)){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
    
    // union(): n1과 n2 합치는 함수 
    static void union(int n1, int n2){
        int r1 = find(n1);
        int r2 = find(n2);
        if(r1 == r2){
            return; //이미 같은 집합이라면
        }
        computers[r1] = r2;
    }
    
    //find(): 부모 노드 return
    static int find(int n){
        if (computers[n] == n){
            //자기자신이 루트라면
            return n;
        }
        //경로 압축 : 부모를 루트로 직접 연결
        return computers[n] = find(computers[n]);
    }

}

2. 프로그래머스 lv2. 올바른 괄호

아이디어
스택을 활용해서 '('가 들어가면 push() , ')'가 들어가면 pop()을 해서 isEmpty()로 출력하기

• String을 Char로 쪼갠 Array로 나타내기 (toCharArray())

import java.util.*; 
class Solution{
	boolean solution(String s){
    	Stack<Character> stack = new Stack<>(); 
        
        for (char c: s.toCharArray()){
        	if (c == '(') stack.push(c); 
            else{
            	if (stack.isEmpty()) return false; 
                stack.pop(); 
            }
        }
        return stack.isEmpty(); 
    }

}