2022-06-22 [3회차] 알고리즘 스터디

1.스도쿠 - DFS, 재귀함수 (골드 4)

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

  Sol) 스터디원 코드 - 스터디원 블로그

<hide/>

/**
0 4 0 0 0 0 2 0 0
0 6 0 0 0 5 0 0 0
2 0 5 0 8 0 0 0 7
0 0 6 0 0 0 0 0 0
5 0 7 0 0 1 9 0 0
0 0 0 0 4 0 0 1 0
0 0 0 3 0 0 0 0 8
0 2 0 0 0 0 0 0 0
9 0 1 0 0 4 7 0 0
 * 
0 0 0 0 0 0 0 0 0
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
0 0 0 0 0 0 0 0 0
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
0 0 0 0 0 0 0 0 0
 * 
 * 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
 */

import java.io.*;
import java.util.*;

//596ms
public class Boj2580 {
    static int[][] grid;

    public static void main(String[] args) throws IOException {
        // grid = new int[9][9];
        // BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // for (int i = 0; i < grid.length; i++) {
        // String[] inputs = bf.readLine().split(" ");
        // for (int j = 0; j < inputs.length; j++) {
        // grid[i][j] = Integer.parseInt(inputs[j]);
        // }
        // }
        // dfs(0, 0);
        // bf.close();
        // Boj2580_02 s = new Boj2580_02();
        // s.main();
        // Boj2580_03 s = new Boj2580_03();
        Boj258_04 s = new Boj258_04();
        s.main();
    }

    public static void dfs(int row, int col) {
        if (col == 9) { // done with this row
            dfs(row + 1, 0);
            return;
        }
        if (row == 9) { // end of this recursion
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(grid[i][j]).append(' ');
                }
                sb.append('\n');
            }
            System.out.println(sb.toString());
            System.exit(0);
        }

        if (grid[row][col] == 0) {
            for (int i = 1; i < 10; i++) {
                if (checker(row, col, i)) {
                    grid[row][col] = i;
                    dfs(row, col + 1);
                }
            }
            grid[row][col] = 0; // go back
            return;
        }
        dfs(row, col + 1);
    }

    public static boolean checker(int row, int col, int val) {
        // Column check
        for (int i = 0; i < 9; i++) {
            if (grid[i][col] == val)
                return false;
        }
        // row check
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] == val)
                return false;
        }
        // 3*3 check
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (grid[i][j] == val)
                    return false;
            }
        }
        return true;
    }
}

// 392ms
class Boj2580_02 {
    static int[][] grid;

    public void main() throws IOException {
        grid = new int[9][9];
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < grid.length; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                grid[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        solve(0);
        System.out.println("done");
        StringBuffer sb = new StringBuffer();
        for (int[] g : grid) {
            for (int x : g) {
                sb.append(x + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    public boolean solve(int cur) {
        if (cur == 81)
            return true;
        int row = cur / 9;
        int col = cur % 9;
        if (grid[row][col] != 0)
            return solve(cur + 1);
        boolean[] flag = new boolean[10];
        validCheck(row, col, flag);
        for (int i = 1; i < 10; i++) {
            if (flag[i]) {
                grid[row][col] = i;
                if (solve(cur + 1)) {
                    return true;
                }
            }
        }
        grid[row][col] = 0;
        return false;
    }

    public void validCheck(int row, int col, boolean[] flag) {
        Arrays.fill(flag, true);
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] != 0)
                flag[grid[row][i]] = false;
            if (grid[i][col] != 0)
                flag[grid[i][col]] = false;
            int r = (row / 3) * 3 + i / 3;
            int c = (col / 3) * 3 + i % 3;
            if (grid[r][c] != 0)
                flag[grid[r][c]] = false;
        }
    }
}

// 500ms
class Boj2580_03 {
    static int[][] grid;

    public void main() throws IOException {
        grid = new int[9][9];
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < grid.length; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                grid[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        solve(0);

        System.out.println("done");

        StringBuffer sb = new StringBuffer();
        for (int[] g : grid) {
            for (int x : g) {
                sb.append(x + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    public boolean solve(int n) {
        if (n == 81)
            return true;
        int row = n / 9;
        int col = n % 9;
        if (grid[row][col] != 0) {
            return solve(n + 1);
        } else {
            for (int i = 1; i < 10; i++) {
                if (isValid(row, col, i)) {
                    grid[row][col] = i;
                    if (solve(n + 1))
                        return true;
                    grid[row][col] = 0;
                }
            }
            return false;
        }
    }

    public boolean isValid(int row, int col, int val) {
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] == val ||
                    grid[i][col] == val ||
                    grid[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == val) {
                return false;
            }
        }
        return true;
    }
}

// 488ms
class Boj258_04 {
    static int[][] grid;

    public void main() throws IOException {
        grid = new int[9][9];
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < grid.length; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < inputs.length; j++) {
                grid[i][j] = Integer.parseInt(inputs[j]);
            }
        }
        solve(0, 0);

        System.out.println("done");

        StringBuffer sb = new StringBuffer();
        for (int[] g : grid) {
            for (int x : g) {
                sb.append(x + " ");
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    public boolean solve(int row, int col) {
        if (col >= 9) {
            col = 0;
            row += 1;
        }
        if (row == 9) {
            return true;
        }
        if (grid[row][col] != 0)
            return solve(row, col + 1);
        for (int i = 1; i < 10; i++) {
            if (validCheck(row, col, i)) {
                grid[row][col] = i;
                if (solve(row, col + 1)) {
                    return true;
                } else {
                    grid[row][col] = 0;
                }
            }
        }
        return false;
    }

    public boolean validCheck(int row, int col, int val) {
        for (int i = 0; i < 9; i++) {
            if (grid[row][i] == val ||
                    grid[i][col] == val ||
                    grid[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == val)
                return false;
        }
        return true;
    }
}

    - .. 아직 이해를 못 했다. 복습 꼭 하기..

  출처:  https://gist.github.com/Guiwoo

 

2. 영역 구하기 (실버 1) - DFS, BFS

 

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

  MySol) - 272ms

<hide/>

// x, y  <=> 행렬 변환

/*

[입력]
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

0 1 2 3 4 5 6
1
2
3
4

(x1, y1) (x2, y2) => (height - y1, x1) (height - y1, x2) => 행렬
(0, 2) (4, 4) => (3, 0) (1, 4)
(1, 1) (2, 5) => (4, 1) (0, 2)
(4 ,0) (6, 2) => (5, 4) (3, 6)

X -> 열 그대로
Y -> height - y 이 행이 된다.

[출력]
3
1 7 13

 */

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Prac2 {

    static int width = 0;
    static int height = 0;
    static int MAX_COUNT = 201; // M, N에 대해 2배 보다 좀 더 크게 잡아야 오류가 안 난다.
    static int[][] AdjMat = new int[MAX_COUNT][MAX_COUNT];
    static int[][] Visited = new int[MAX_COUNT][MAX_COUNT];

    static int[][] DirMat = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int[] cntArr = new int[MAX_COUNT];   // 초기화 시키지 않으면 오류!
    static int idx = 0;

    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        height = scan.nextInt();    // 5
        width = scan.nextInt();     // 7
        int n = scan.nextInt();


        for(int i = 0; i < n; ++i){

            int x1 = scan.nextInt(); // 열 그대로
            int y1 = scan.nextInt(); // height - b 가 행이 된다.
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();

            for(int x = x1; x < x2; ++x){
                for(int y = y1; y < y2; ++y){
                     AdjMat[height - y - 1][x] = 1;
                }
            }
        }
        // 방문행렬 0으로 해줘여 되너????
        for(int i = 0; i < height; ++i){
            for(int j = 0; j < width; ++j) {
                Visited[i][j] = 0;
            }
        }

        for(int i = 0; i < height; ++i){
           for(int j = 0; j < width; ++j){
                if( AdjMat[i][j] == 0 && Visited[i][j] == 0) {     //  ???????    //방문행렬 안 넣으면 오류
                    ++idx;
                    DFS(i, j);
                }
           }
        }

        int[] res = new int[idx];

        for(int i = 1; i <= idx; ++i){
            res[i - 1] = cntArr[i];
        }
        Arrays.sort(res);

        System.out.println(idx);

        for(int r : res){
            System.out.print(r + " ");
        }

/* 인접행렬 확인용
           for(int i = 0; i < height; ++i){
                for(int j = 0; j < width; ++j){
                    System.out.print(AdjMat[i][j] + " ");
                }
                System.out.println();
            }
 */
    }

    public static void DFS(int _row, int _col){
        ++cntArr[idx];
        Visited[_row][_col] = 1;    // 방문 등록

        for(int i = 0; i < 4; ++i){

            int nextRow = _row + DirMat[i][0];
            int nextCol = _col + DirMat[i][1];

            if(nextRow < 0 || height <= nextRow ||  // 행, 열이 범위 밖에 있는 경우
               nextCol < 0 || width <= nextCol){
                continue;
            }

            if(1 == Visited[nextRow][nextCol]){     // 위에 if문이랑 따로 써줘야 오류가 안 난다.
                continue;
            }

            if(AdjMat[nextRow][nextCol] == 0){
//              System.out.printf("cntArr[%d] = %d (%d, %d) -> (%d, %d)%n",idx, cntArr[idx], _row, _col, nextRow, nextCol);
                DFS(nextRow, nextCol);
            }
        }
    }
}

    - (x1, y1), (x2, y2)가 입력되면 => (height - y1 - 1, x1) 부터  (height - y2 - 1, x2) 까지의 영역에 1이 칠해진다.

    - DFS로 풀면 BFS와 다르게 Queue와while문을 쓰지 않고 DFS메서드를 재귀함수로 돌리면 된다. 

    - XY평면 좌표를 행렬로 변환하는데 시간이 꽤 오래 결렸다.

    - DFS메서드 내의 for문 안에서 nextCol, nextRow에 대한 탈출 조건을 가장 먼저 작성해야한다.

      -> 그래야만 다음 탈출 조건인 if문에 대해 Visited[nextRow][nextCol] 행렬에 값을 대응시킬 수 있다. 

       -> 이 부분 때문에 NPE가 나서 오래 헤멨다.

     - MAX_COUNT는 문제에서 정해준 범위의 (M, N <= 100) 2배 보다 조금 더 크게 해줘야 런타임 에러(ArrayIndexOutOfBounds)가 나지 않는다. 

    - 또한, AdhMat를 돌면서 DFS를 실행하기 전에 if문 조건에 인접행렬, 방문행렬 조건을 둘다 추가해줘야 오류가 나지 않는다.

    - 좌표평면 -> 행렬 변환

    - (x, y) 좌표평면을 행렬로 바꾸는 부분에서 시간이 오래 걸렸다.

 

  Sol) 스터디원 코드 - 140ms

<hide/>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

// 백준 2583번
// https://www.acmicpc.net/problem/2583
public class Practice070 {
    public static ArrayList<Integer> area; // 각 분리된 부분의 넓이 배열
    public static int areatmp; // 재귀돌면서 넓이 저장할 변수
    public static int[][] grid; // 땅
    public static void dfs(int[][] grid, int i, int j) {
        int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}}; // 동서남북
        grid[i][j] = 1; // 1로 바꾸고 (방문배열이 필요한 경우도 있음)
        areatmp++; // 넓이 더하기
        for (int[] d : dir) {
            int x = i + d[0];
            int y = j + d[1];
            // 그리드 안에 있으면서, 0인 경우
            if(x>=0 && y>=0 && x<grid.length && y<grid[0].length && grid[x][y]==0) {
                dfs(grid, x, y); // 재귀호출
            }
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m, n, times;
        String[] tmp1 = br.readLine().split(" ");
        m = Integer.parseInt(tmp1[0]);
        n = Integer.parseInt(tmp1[1]);
        times = Integer.parseInt(tmp1[2]);

        grid = new int[m][n];
        area = new ArrayList<>();

        // 배열에 1 집어넣기
        for (int i = 0; i < times; i++) {
            int x1, x2, y1, y2;
            String[] tmp2 = br.readLine().split(" ");
            x1 = Integer.parseInt(tmp2[0]);
            y1 = Integer.parseInt(tmp2[1]);
            x2 = Integer.parseInt(tmp2[2]);
            y2 = Integer.parseInt(tmp2[3]);
            for (int j = y1; j < y2; j++) { // <- for문을 돌때
                for (int k = x1; k < x2; k++) { // <- 미리 배열의 인덱스를 제대로 처리해보자
                    grid[j][k] = 1;
                }
            }
        }

        // 배열 돌면서 0이면 dfs돌기
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==0) {
                    dfs(grid, i, j);
                    area.add(areatmp);
                    areatmp = 0;
                }
            }
        }
        // 출력
        area.sort(Comparator.naturalOrder());
        System.out.println(area.size());
        for (int i = 0; i < area.size(); i++) {
            System.out.print(area.get(i) + " ");
        }
    }
}

    - 내 코드보다 훨씬 간결하고 시간 면에서 효율적인 코드이다.

    - 스터디원 코드를 확인해보니 출력 값을 저장하기 위해 크기가 고정된 배열 cntArr보다는 ArrayList를 쓰는 게 더 적합하다는 걸 느꼈다.

    - 그리고 이 문제의 경우 방문행렬을 굳이 만들지않고 인접행렬을 그대로 이용해도 된다는 걸 알았다.

 

  Note) 입출력 예시

<hide/>
[입력]
5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

[출력]
3
1 7 13

 

 

3. 랜선 자르기 (실버 2) -  N개를 만들 수 있는 랜선의 최대 길이를 출력  - Binary Search

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

  - 이진 탐색 이용 한다.

  - 이진 탐색을 생각하지 못해서 answer를 하나씩 줄이는 방법을 이용했는데 테스트 케이스도 맞았는데 오답이라고 나온다. 

    -> 오버플로우와 시간 초과로 인해 오답이 난 걸로 보인다. 

    -> 오버플로우(랜선 길이는 최대 2^31 - 1)를 해결하기 위해 int -> long으로 바꾸고 이진 탐색을 이용한다.

 

   MySol)  스터디원 코드 변수명만 수정 - 472ms

<hide/>import java.util.Arrays;
//
//4 11
//        802
//        743
//        457
//        539
// 출력 200

import java.util.Locale;
import java.util.Scanner;

// 랜선 자르기
public class Test4 {


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int K = scanner.nextInt();  // 현재 랜선 개수 4
        int N = scanner.nextInt();  // 자르고 나서 랜선의 개수  11
        long totalLength = 0;   // 랜선 길이의 합
        long[] lanCableArr = new long[K];

        for(int i = 0; i < K; ++i){
            lanCableArr[i] = scanner.nextLong();    // 802 743 457 539
        }

        totalLength = Arrays.stream(lanCableArr).sum();
        long left = 1;
        long right =  totalLength / N;  // 가능한 최댓값
        long maxLength = -1;  // 이게 꼭 필요? 0으로 하면 오류가 난다. 이유는 ?

        while(left <= right){       // mid 의 최댓값을 구하고 싶다!

            long mid = (left + right) / 2;   // 자르는 단위를 중간값으로 변경한다.
            int cnt = 0;

            for(long lan : lanCableArr){
                cnt += (int) (lan / mid);
            }
            if(cnt >= N){       // N을 초과한다는 것은? mid가 짧으니 mid를 늘린다.
                left = mid + 1; // 자르는 단위를 늘리면 cnt가 줄어든다
                maxLength = mid;    // 단위가 mid일 때 cnt가 범위를 만족하므로 저장한다.

            }else {
                right = mid - 1;        // 자르는 단위를 줄이면 cnt가 늘어나도록 할 수 있다.
            }
        }

        System.out.println(maxLength);
    }
}

    - 오류가 계속 나서 수정해봤는데  maxLength의 초깃값을 0이 아닌 Long.MIN_VALUE로 설정하면 통과된다.(최대 길이를 구하는게 문제이므로 길이를 일단 짧게 잡아야한다.)

      -> 0보다 작은 값을 초깃값으로 정하면 통과된다. (중요!)

      -> maxLength는 나중에 당연히 바뀔텐데 왜 초깃값이 영향을 주는 건지 모르겠다.(아마 바뀌지 않는 경우도 고려해야하는 것 같다.)

 

  Sol) 스터디원 코드

<hide/>
import java.*;
public class Main {

    public static void main(String[] args) throws Exception {
       
        Scanner scanner = new Scanner(System.in);
        int K = scanner.nextInt();  // 반복 횟수 4
        int N = scanner.nextInt();  // 필요한 랜선의 개수  11

        long totalLength = 0;   // 랜선 길이의 합
        long[] lanCableArr = new long[K];

        for(int i = 0; i < K; ++i){
            long lanCable = scanner.nextLong();
            lanCableArr[i] = lanCable;
            totalLength += lanCable;    //
        }

        long left = 1;
        long right = totalLength / N;
        long maxLength = Long.MIN_VALUE;    // 일단 최솟값으로 잡는다.

        while(left <= right){

            long mid = (left + right) / 2;
            int cnt = 0;

            for(int  i = 0;i < lanCableArr.length; ++i){
                cnt += (int) (lanCableArr[i] / mid);
            }
            if(cnt >= N){   // 너무 많이 자르면?
                left = mid + 1;
                maxLength = mid;
            }else{
                right = mid - 1;
            }
        }
        System.out.println(maxLength);
    }
}

 

 

4. 정수 삼각형 (level 3) - Dynamic Programming

출처: https://programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

  Sol 1) 위에서 아래로 내려가는 방법

<hide/>
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        for(int i = 1; i < triangle.length; ++i){
            for(int j = 0; j < triangle[i].length; ++j){
                if(j == 0){			// 가장 첫번째 열
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j];
                }else if(i == j){	// 가장 오른쪽 열
                    triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
                }else{
                    int left = triangle[i][j] + triangle[i-1][j-1];
                    int right = triangle[i][j] + triangle[i-1][j];
                    triangle[i][j] = Math.max(left, right);
                }
                answer = Math.max(answer, triangle[i][j]);
            }
        }
        return answer;
    }
}

  - 이차원 배열을 그대로 둔채로 값을 더하면서 max를 구한다.

  - 0행 -> 1행으로 넘어가면서 위 행의 left와 right를 더해주면서 더 큰 값을 answer로 정한다. (사실, 밑에서 위로 올라가는 게 더 간단함)

  - 낮은 난이도의 동적계획법 문제이다.

  - 삼각형 배열 문제 자주 나오는 편이다.

 

  Sol 2) 밑에서부터 위로 올라가는 방밥

<hide/>
class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        for(int i = triangle.length - 2; i >= 0 ; --i){
            for(int j = 0; j < triangle[i].length; ++j){
                    int left = triangle[i][j] + triangle[i+1][j];
                    int right = triangle[i][j] + triangle[i+1][j+1];
                    triangle[i][j] = Math.max(left, right);
            }
        }
        return triangle[0][0];
    }
}

 

[3주차] Coding Test 해시 / BFS / DFS / 동적계획법