KB IT’s Your Life 4기 - Java 알고리즘 15일차

- 백준 7562 나이트의 이동(BFS)
- 백준 1697 숨바꼭질(BFS)
- 백준 2667 단지번호붙이기(BFS)
- 백준 14502 연구소(BFS)

- 백준 2661 좋은수열(백트래킹)
- 백준 1486 장훈이의 높은 선반(백트래킹)

- 백준 4195 친구네트워크(유니온파인드)

import java.util.Arrays;
import java.util.Scanner;


// 01. 철수 친구는 내 친구 
// 유니온 파인드를 활용해 철수와 친구(연결된) 의 수를 구하는 문제
//
// 문제 조건 중 "철수를 제외하고" 붙어있음 -> 항상 문제 꼼꼼히 읽기 
//
// 1. 입력으로 들어온 친구관계를 이용해 union 연산을 통해 연결
// 2. 철수(1번)와 친구(연결된)인 마을사람을 find 연산을 통해 카운트   

public class 알고리즘1번_Sol {
    
    // 유니온파인드에서 사용할 부모노드를 알려줄 배열
    static int [] parent;
    
    // find 연산 = x 의 루트노트 찾아줌
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }
 
    // union 연산 = (x,y) 연결
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        // 부모 배열 초기화
        parent = new int [N+1];
        Arrays.setAll(parent, i -> i);
        
        // 친구들끼리 유니온 연산
        for(int i=0; i<M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            union(u,v);
        }
        
        // 철수의 친구 수
        int cnt = 0;
        
        // find 연산으로 1번(철수)과 친구인 마을사람 카운트 
        for(int i=2; i<N+1; i++) {
            if(find(1) == find(i)) cnt++;
        }
        
        // 정답 출력
        System.out.println(cnt);
        
    }

}

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

public class 알고리즘_2번 {
    static int M, N, cnt;                    //    열, 행, 저글링개수 카운트
    static int[][] arr, v;
    static int[] di = {-1,1,0,0};
    static int[] dj = {0,0,-1,1};
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));    //    파일로부터 읽기
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N+2][M+2];            //    외부에 여분공간처리
        v = new int[N+2][M+2];                //    외부에 여분공간처리

        cnt = 0;
        for (int i=1; i<=N; i++) {
            String line = br.readLine();
            for (int j=0; j<M; j++) {
                arr[i][j+1] = (int)(line.charAt(j)-'0');
                if(arr[i][j+1]==1) cnt++;    //    1인 개수 카운트
            }
        }

        st = new StringTokenizer(br.readLine());
        int SJ = Integer.parseInt(st.nextToken());//코로나 감염학생 좌표
        int SI = Integer.parseInt(st.nextToken());//코로나 감염학생 좌표
        
        int ans = bfs(SI, SJ);
        System.out.println(ans);
        System.out.println(cnt);
    }
    
    public static int bfs(int si, int sj) {
        Queue<Pos> q = new LinkedList<>();

        q.add(new Pos(si,sj));
        v[si][sj] = 3;                        //    시작위치에 3 (3초후 저글링 사망)
        cnt--;

        Pos c = null;
        while (!q.isEmpty()) {
            c = q.poll();
            for (int k=0; k<4; k++) {//4방향 검색
                int ni = c.i + di[k];
                int nj = c.j + dj[k];
                if (v[ni][nj]==0 && arr[ni][nj]>0) {//미방문 & 학생있으면
                    v[ni][nj] = v[c.i][c.j]+1;
                    q.add(new Pos(ni,nj));
                    cnt--;//감영학생발생으로인해 정상학생수 감소
                }
            }
        }
        return v[c.i][c.j];
    }
}
class Pos{
    public int i, j;
    Pos(int i, int j){
        this.i = i;
        this.j = j;
    }
}

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

public class 알고리즘_3번 {
    static int N, M, ans;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        //    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));    //    파일로부터 읽기
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N+2];
        st = new StringTokenizer(br.readLine());
        for (int i=1;i<=N;i++) {
            arr[i]=Integer.parseInt(st.nextToken());
        }

        ans = 0;
        dfs(0, 0, 1);
        System.out.println(ans);
    }

    public static void dfs(int n, int m, int sum) {
        if (n>N || m==M+1) {
            return;
        }
        ans = Math.max(ans, sum);
        
        if (n<=N-1) {
            dfs(n+1, m+1, sum+arr[n+1]);    //    굴리는 경우
        }
        if (n<=N-2) {
            dfs(n+2, m+1, sum/2+arr[n+2]);    //    던지는 경우
        }
    }
}