1. 색종이 붙이기 - 백트래킹
출처 https://www.acmicpc.net/problem/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/
문제 가져온 스터디원 블로그 - 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가 제시되시 않는다.
'자료구조와 알고리듬 With Java > [Study] BAEKJOON 프로그래머스 CodeUp LeetCode' 카테고리의 다른 글
[09월 1주차] 알고리즘 스터디 (0) | 2022.09.05 |
---|---|
2022-08-28 [11회차] 알고리즘 스터디 (0) | 2022.08.28 |
2022-07-27 [8회차] 알고리즘 스터디 (0) | 2022.07.26 |
2022-07-20 [7회차] 알고리즘 스터디 (0) | 2022.07.20 |
[백준][프로그래머스] 다이나믹 프로그래밍 (0) | 2022.07.13 |