2022-08-03 [9회차] 알고리즘 스터디

1. 색종이 붙이기 - 백트래킹

출처 https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

  Sol) 476ms

<hide/>
// 색종이 붙이기
import java.util.Arrays;
import java.util.Scanner;
public class Practice1 {

    static int [] paper = {0, 5, 5, 5, 5, 5};	// 사이즈 1 ~ 5까지 붙일 수 있는 색종이
    static int min = Integer.MAX_VALUE;
    static int[][] matrix = new int[10][10];

    // 색종이를 붙이거나 뗄 때 배열의 값을 target으로 바꿔준다.
    public static void change(int _row, int _col, int size, int target){
        for(int i = _row; i < _row + size;++i){
            for(int j = _col; j < _col + size; ++j){
                matrix[i][j] = target;
            }
        }
    }

    // 사이즈 범위 내의 값이 모두 1이어야 크기가 size인 색종이를 붙일 수 있다.
    public static boolean Stickable(int _row, int _col, int size){
        for(int i = _row; i < _row + size; ++i){
            for(int j = _col; j < _col + size; ++j){
                if(i >= 10 || j >= 10){
                    return false;
                }
                if(matrix[i][j] != 1){
                    return false;
                }
            }
        }
        return true;
    }
    
/* 확인용 출력 메서드
    public static void print(){
        for(int [] m : matrix){
            System.out.println(Arrays.toString(m));
        }
        System.out.println();
    }
*/

    public static void DFS(int _row, int _col, int cnt) {   // cnt는 색종이 개수
//            System.out.println("row " + _row + " col " + _col  + " cnt " +cnt);

        // 마지막까지 탐색 끝난 경우, 딱 한 번 실행된다.
        if(_row == 9 && _col == 10){
            min = Math.min(min, cnt);
            return;
        }

        // 더 이상 탐색할 필요가 없는 경우
        // 색종이를 붙이는 여러 방법 가운데 min값을 넘으면 DFS들어갈 필요 없으니 return
        //안 넣어도 정답인데 50ms 더 걸린다.
        if(min <= cnt){
            return;
        }

        // 각 행에서 맨 오른쪽까지 탐색한 경우, 아래 행으로 이동한다.
        if(_col == 10){
            DFS(_row + 1,  0, cnt);
            return;
        }

        // 색종이 붙여야하는 경우
        if(matrix[_row][_col] == 1){
            for(int i = 5; i >= 1; --i){        // 큰 것부터 붙여야 최소 개수 나온다.
                if(paper[i] > 0 && Stickable(_row, _col, i)){
                    change(_row, _col, i, 0);   // 색종이 붙인다.
                    --paper[i];
                    DFS(_row, _col, cnt + 1);
                    change(_row, _col, i, 1);   // 색종이를 뗀다. 떼지 않으면 색종이 붙이는 영역끼리 붙어있을 때, -1반환될 수 있다.. 
                    ++paper[i];					// 방금, 붙인 색종이를 다시 뗀 경우도 확인한다.
                }
            }
        // 0이라서 붙일 필요 없는 경우
        }else{
            DFS(_row, _col + 1, cnt);   // 다음 칸으로 이동한다.
        }
    }

    public static void main(String[] args){

        Scanner scan = new Scanner(System.in);
        for(int i = 0; i < 10; ++i){
            for(int j = 0; j < 10; ++j){
                matrix[i][j] = scan.nextInt();
            }
        }
        DFS(0, 0, 0);

        if(min == Integer.MAX_VALUE){   // 불가능한 경우
            System.out.println(-1);
        }else{
            System.out.println(min);
        }
    }
}

    - 두 가지 메서드를 먼저 만든다.

    1) 색종이를 붙이거나 뗄 때 배열의 값을  target으로 바꿔주기 위한 change() 

    2) 어떤 위치에서 특정 사이즈의 색종이를 붙일 수 있는지 나타내는 boolean 메서드 Stickable()

 

    - DFS메서드에서는 2차원 배열에 대해 0행 0열 부터 한 칸씩 모두 돌면서 색종이를 붙일 수 있는지 확인하면서 cnt를 함께 카운트해준다. 

    - 색종이를 큰 것 부터 붙여야 최소한의 개수를 반환할 수 있으니 사이즈 5부터 1까지 차례대로 붙인다.

    - 그리고 색종이를 붙일 수 있는 경우에는 색종이를 붙이는 경우와 붙이지 않는 경우에 대해 모두 확인하기 위해 DFS()전 후로 색종이를 붙였다가 떼도록 한다. 

    - 색종이를 붙일 수 없는 경우에는 다음 칸으로 DFS()을 실행하도록 한다.

 

 

 

2. Linked List Cycle II - 토끼과 거북이 알고리즘

출처 https://leetcode.com/problems/linked-list-cycle-ii/

Linked List Cycle II - LeetCode

문제 가져온 스터디원 블로그 - https://guiwoo.tistory.com/

  Sol)

<hide/>
class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null)return null;
        while(head != null && head.val != 1<<30){
            head.val = 1<<30;
            head = head.next;
        }
        if(head == null) return null;
        return head;
    }
}
class Solution2 {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode pointer = head;
        while(pointer != null){
            if(!set.add(pointer)){
                return pointer;
            }
            pointer = pointer.next;
        }
        return null;
    }
}

class Solution3 {	// 투포인터
    public ListNode detectCycle(ListNode head) {
        if(head==null)return null;
        ListNode slow=head,fast=head;
        while(fast.next!=null&&fast.next.next!=null){
            // slow , fast move
            fast=fast.next.next;
            // slow = 1 3 5
            // fast = 2 4 6
            slow=slow.next;
            if(fast==slow){
                while(head!=fast){
                    head=head.next;
                    fast=fast.next;
                }
                return fast;
            }
        }
        return null;
    }
}

    - 3번 솔루션은 언젠가는 만나니까 투포인터로 풀 수 있다.

    - 플로이드 워셜로도 풀 수 있다.

    - 매개변수로  pos가 제시되시 않는다.