DFS와 BFS > 7576번, 1389번

7576번

 

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

// 1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않음
// 보관 후 하루 지나면 익은 토마토의 상하좌우에 있는 익지 않은 토마토가 익는다 (bfs 사용)
// 익은 토마토의 개수가 여러개인 경우도 있으므로 동시 출발 > 큐 사용

public class baekjoon7576 {

    // 이동할 4가지 방향 정의 (상하 / 좌우가 겹치지 않게)
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int n;
    static int m;
    static int [][] grid;
    static Queue<Tomato> queue = new LinkedList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        grid = new int[n+1][m+1];
        for(int i = 1; i<n+1; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 1; j<m+1; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m+1; j++) {
                if(grid[i][j] == 1) { // 익은 토마토가 있는 지점들을 모두 큐에 넣어준다
                    queue.offer(new Tomato(i,j));
                }
            }
        }
        bfs();
        int result = 0;
        Loop: for(int i = 1; i<n+1; i++) {
            for(int j = 1; j<m+1; j++) {
                if(grid[i][j] == 0) { // 토마토가 모두 익지 못한 경우
                    result = -1;
                    break Loop;
                }
                if(grid[i][j] > result) { // grid 값 중 가장 큰 값에서 1을 뺀 값이 모두 익을 때까지의 최소 날짜
                    result = grid[i][j];
                }
            }
        }
        if(result == -1) {
            System.out.println(-1);
        } else {
            System.out.println(result - 1);
        }
    }

    public static void bfs () {
        while(!queue.isEmpty()) {
            Tomato tomato = queue.poll();
            int x= tomato.x;
            int y= tomato.y;

            for(int i = 0; i<dx.length; i++) {
                int xx = x+ dx[i];
                int yy = y+ dy[i];
                if(check(xx, yy) && grid[xx][yy] == 0) { // 상자를 벗어나지 않고 토마토가 익지 않았다면
                    grid[xx][yy] = grid[x][y] + 1;
                    queue.offer(new Tomato(xx, yy));
                }
            }
        }
    }

    public static boolean check(int x, int y) {
        // 상자 밖을 벗어나지 않아야 한다
        if (x < 1 || x > n || y < 1 || y > m) {
            return false;
        }
        return true;
    }
}

class Tomato {
    int x;
    int y;
    Tomato (int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

1389번

 

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


// 유저의 수 = 정점의 개수
// 친구 관계의 수 = 간선의 개수
// A와 B가 친구이면, B와 A도 친구 > 양방향

// 인접리스트 사용한 풀이
// 두 사람이 최소 몇 단계만에 이어질 수 있는지
// 1번 유저의 케빈 베이컨의 수
// (1번 유저 -> 2번 유저) + (1번 유저 -> 3번 유저) + (1번 유저 -> 4번 유저) + (1번 유저 -> 5번 유저)

public class baekjoon1389_ {

    static boolean [] visited;
    static ArrayList<Kevin> [] lists;
    static int n;
    static int m;
    static int result;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        lists = new ArrayList[n+1];
        for(int i = 1; i<=n; i++) {
            lists[i] = new ArrayList<>();
        }
        for(int i = 1; i<=m; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            lists[a].add(new Kevin(b, 0));
            lists[b].add(new Kevin(a, 0));
        }
        for(int i = 1; i<=n; i++) {
            visited = new boolean[n+1];
            bfs(i);
        }
        System.out.println(result);
    }
    public static void bfs (int x) {
        Queue <Kevin> queue = new LinkedList<>();
        visited[x] = true;
        int count= 0; // 각 유저들을 돌면서 얻은 결과 값 (1번 유저의 케빈 베이컨의 수, 2번 유저의 케빈 베이컨의 수...)
        queue.offer(new Kevin(x, 0));
        while(!queue.isEmpty()) {
            Kevin kevin = queue.poll();
            count += kevin.value;
            for(Kevin k : lists[kevin.num]) {
                if(!visited[k.num]) {
                    visited[k.num] = true;
                    queue.offer(new Kevin(k.num, kevin.value+1));
                }
            }
        }
        if(min > count) { // 최솟값을 구하기 위해
            min = count;
            result = x;
        }
    }
}

class Kevin {
    int num;
    int value;

    Kevin (int num, int value) {
        this.num = num;
        this.value = value;
    }
}