알고리즘 재활 3일차 - 백준 15652, 2636번

 

플젝하면서도 꾸준히 할껄.. 할껄.. 라고 할때 할껄.. 할...

 

N과 M (4)

 

 

중복이 안되게, 앞수보다는 뒤 수가 더 크게 수열을 만들어 주면 된다.

숫자 길이에 맞게 depth를 짜주고, start로 중복을 막아주어 수열을 뽑아내면 꿋.

 

import java.io.*;
import java.util.*;
 
public class Main { // S3 N과 M(3)
    static int N, M;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();
 
    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());
        arr = new int[M];
        dfs(0, 1);
        System.out.println(sb);
    }
 
    public static void dfs(int depth, int start) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }
        // start 변수로 중복 방지
        for (int i = start; i <= N; i++) {
            arr[depth] = i;
            dfs(depth + 1, i);
        }
    }
}

 

---

치즈

 

 

외부 공기와 두면 이상 맞닿은 치즈는 녹고만다..

이 치즈들이 다 녹는데 얼마나 걸리는지 시간을 구하는 문제다.

요즘 너무 덥잖아요 그쵸?

아 더워

 

가장 중요한 포인트는 외부 공기와 치즈에 감싸진 내부 공기를 구별하는것이다.

어떻게 작성할지 sudo 코드를 간단하게 작성해 풀었다.

 

 

코드가 굉장히.. 장황하게 나왔다.

 

import java.io.*;
import java.util.*;
 
public class Main { // G3 치즈
    static int N, M, cheeseCnt;
    static int[][] cheese;
    static boolean[][] visited;
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static StringBuilder sb = new StringBuilder();
 
    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());
        cheese = new int[N][M];
        cheeseCnt = 0;
        int time = 0;
 
        // input
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                cheese[i][j] = Integer.parseInt(st.nextToken());
                if (cheese[i][j] == 1) {
                    cheeseCnt++;
                }
            }
        }
 
        while (cheeseCnt != 0) {
            // 외부 공기 체크
            outsideAir(0, 0);
            bfs(0, 0);
//            showmetheMap();
            time++;
        }
 
        System.out.println(time);
    }
 
    // 치즈 탐색 로직
    public static void bfs(int r, int c) {
        visited = new boolean[N][M];
        Queue<int[]> que = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (cheese[i][j] != 1 || visited[i][j]) {
                    continue;
                }
                que.add(new int[]{i, j});
                visited[i][j] = true;
            }
        }
        while (!que.isEmpty()) {
            int[] now = que.poll();
            int nowR = now[0];
            int nowC = now[1];
            // 근처 외부공기 2면 이상 맞닿으면 외부공기로 전환
            if (nearAirchk(nowR, nowC)) {
                cheese[nowR][nowC] = 2;
                cheeseCnt--;
            }
            for (int k = 0; k < 4; k++) {
                int nextR = nowR + dr[k];
                int nextC = nowC + dc[k];
                if (!rangeChk(nextR, nextC) || cheese[nextR][nextC] != 1) {
                    continue;
                }
                visited[nextR][nextC] = true;
                que.add(new int[]{nextR, nextC});
            }
        }
    }
 
    // 외부공기인지 판단
    public static void outsideAir(int r, int c) {
 
        visited = new boolean[N][M];
        Queue<int[]> que = new ArrayDeque<>();
        que.add(new int[]{0, 0});
        visited[0][0] = true;
        while (!que.isEmpty()) {
            int[] now = que.poll();
            int nowR = now[0];
            int nowC = now[1];
            if (cheese[nowR][nowC] == 0) {
                cheese[nowR][nowC] = 2;
            }
            for (int k = 0; k < 4; k++) {
                int nextR = nowR + dr[k];
                int nextC = nowC + dc[k];
                if (!rangeChk(nextR, nextC) || cheese[nextR][nextC] == 1) {
                    continue;
                }
                    visited[nextR][nextC] = true;
                    que.add(new int[]{nextR, nextC});
            }
        }
    }
 
    // 해당 치즈 주변에 외부공기 있는지 체크
    public static boolean nearAirchk(int r, int c) {
        int cnt = 0;
        for (int k = 0; k < 4; k++) {
            int nextR = r + dr[k];
            int nextC = c + dc[k];
            if (!rangeChk(nextR, nextC)) {
                continue;
            }
            if (cheese[nextR][nextC] == 2) {
                cnt++;
            }
        }
        return cnt >= 2;
    }
 
    public static boolean rangeChk(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < M && !visited[r][c];
    }
 
    public static void showmetheMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                System.out.print(cheese[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}