'recursive'에 해당되는 글 7건

  1. 2022.01.04[TSP1] Traveling Salesman Problem 1
  2. 2022.01.04[NQUEEN] N-Queen
  3. 2022.01.03[SHISENSHO] Shisen-sho
  4. 2022.01.02[CLOCKSYNC] Synchronizing Clocks
  5. 2021.12.30[WEIRD] Weird Numbers
  6. 2021.12.28[BOARDCOVER] 게임판 덮기
  7. 2021.12.27[PICNIC] 소풍

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/TSP1

 

algospot.com :: TSP1

Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
 
public class Main {
    private static final double[][] distances = new double[8][8];
    private static final boolean[] visited = new boolean[8];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    distances[i][j] = scanner.nextDouble();
                }
            }
 
            System.out.printf("%.10f\n", getMinVisitDistance(n));
            Arrays.fill(visited, false);
        }
    }
 
    private static double getMinVisitDistance(int n) {
        double ret = Double.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            visited[i] = true;
            ret = Math.min(ret, getMinVisitDistance(n, i, 1)); // 시작하는 도시마다, 총 방문거리가 달라질 수 있다.
            visited[i] = false;
        }
 
        return ret;
    }
 
    private static double getMinVisitDistance(int n, int cur, int visitedCount) {
        if (visitedCount >= n) return 0// 기저사례 : 모든 도시를 방문
 
        double ret = Double.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            if (cur == i) continue;
            if (visited[i]) continue;
 
            visited[i] = true;
            ret = Math.min(ret, distances[cur][i] + getMinVisitDistance(n, i, visitedCount + 1));
            visited[i] = false;
        }
 
        return ret;
    }
}
cs


이 풀이는 기존에 풀었던 아래 문제와 유사합니다.

 

[PICNIC] 피크닉


완전탐색으로 도시를 방문하는 모든 순서에 따라 총 거리를 구한 뒤, 최소 값을 출력하도록 합니다. 
이 방법은 가장 비효율적이며 도시의 수가 적기 때문(최대 8개)에 가능한 방법입니다.

추 후 메모이제이션을 이용하여 더 빠르게 정답을 구할 수 있는 방법을 소개해보도록 하겠습니다.

 

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

 

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[NQUEEN] N-Queen  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
Posted by N'

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/NQUEEN

 

algospot.com :: NQUEEN

N-Queen 문제 정보 문제 N-Queen 퍼즐은 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 퍼즐이다. (퀸은 체스에서 가장 강력한 기물로, 자신의 위치에서 상하좌우, 그리고 대각선

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;
 
public class Main {
    private static final int[][] boards = new int[12][12];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt();
            System.out.println(getCount(n, 0));
        }
    }
 
    private static int getCount(int n, int y) {
        if (y >= n) return 1;
        int ret = 0;
        for (int x = 0; x < n; ++x) {
            if (boards[y][x] != 0continue;
            put(n, y, x, 1);
            ret += getCount(n, y + 1);
            put(n, y, x, -1);
        }
 
        return ret;
    }
 
    private static void put(int n, int y, int x, int count) {
        boards[y][x] += count;
        for (int i = 1, len = n - y; i < len; ++i) {
            boards[y + i][x] += count;
            if (x - i >= 0) boards[y + i][x - i] += count;
            if (x + i < n) boards[y + i][x + i] += count;
        }
    }
}
cs


이 풀이는 기존에 풀었던 아래 문제와 유사합니다. 

 

[PICNIC] 피크닉


재귀로 행마다 하나의 퀸을 배치해보면 총 경우의 수를 구할 수 있습니다. 
같은 경우의 수를 방지하기 위해, 아래 행을 향하여 공격범위를 기록하며 위에서 아래 행으로만 가짓수를 세도록 합니다.

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
[SHISENSHO] Shisen-sho  (0) 2022.01.03
Posted by N'

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/SHISENSHO

 

algospot.com :: SHISENSHO

Shisen-sho 문제 정보 문제 Shisen-sho(in Korean, Sa-Cheon-Sung 사천성) is a board game that originated in Japan, which is popular in Korea as well. The game is played on a rectangular game board with N \times M cells, and various tiles are placed o

www.algospot.com

 

풀이입니다. 🤔

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.*;
 
public class Main {
    private static final char EMPTY = '.';
    private static final int[][] directions = new int[][]{{-10}, {01}, {10}, {0-1}};
    private static final char[][] boards = new char[50][50];
    private static final boolean[][] foundCoordinates = new boolean[50][50];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int h = scanner.nextInt(), w = scanner.nextInt();
            for (int i = 0; i < h; ++i) {
                char[] line = scanner.next().toCharArray();
                for (int j = 0, len = line.length; j < len; ++j) {
                    boards[i][j] = line[j];
                }
            }
 
            System.out.println(getCount(h, w));
        }
    }
 
    private static int getCount(int h, int w) {
        int ret = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (boards[i][j] == EMPTY) continue;
                for (int k = 0, len = directions.length; k < len; ++k) {
                    find(h, w, i + directions[k][0], j + directions[k][1], boards[i][j], k, 0);
                }
 
                ret += getCount(h, w, i, j);
            }
        }
 
        return ret;
    }
 
    private static void find(int h, int w, int y, int x, char character, int direction, int turnCount) {
        if (turnCount == 3return// 기저사례 1: 경로를 3회 초과로 변경할 수 없다.
        if (y < 0 || y >= h || x < 0 || x >= w) return// 기저 사례 2: 좌표가 주어진 영역을 벗어났다.
        if (boards[y][x] == character) {
            foundCoordinates[y][x] = true;
            return;
        } // 기저사례 3: character 와 동일한 문자를 발견
        if (boards[y][x] != EMPTY) return// 기저사례 4: character 와 동일하지 않고, 빈 문자열이 아닌 문자를 발견
 
        for (int i = 0, len = directions.length; i < len; ++i) {
            find(h, w, y + directions[i][0], x + directions[i][1], character, i, (direction == i) ? turnCount : turnCount + 1);
        }
    }
 
    private static int getCount(int h, int w, int y, int x) {
        int ret = 0;
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (foundCoordinates[i][j]) {
                    foundCoordinates[i][j] = false;
                    if (y > i || (y == i && x > j)) ++ret;  // 중복된 경우를 제거하기 위해, 자신보다 앞에 있는 좌표는 추가하지 않음.
                }
            }
        }
 
        return ret;
    }
}
cs

 

이 문제는 이동할 수 있는 경로를 완전탐색하는 것으로 문제를 해결해볼 수 있습니다.

 

- 경로를 변경할 수 있는 횟수는 최대 3회입니다. (첫 번째 방향 선택도 경로를 선택한 것으로 봅니다.)
- 경로 탐색 중 주어진 W,H 를 넘을 수 없습니다. 
- 경로 탐색 중 빈 칸(.) 이 아닌 문자가 나온다면, 탐색을 멈춥니다. (같은 문자라면, 해당 좌표를 기억해야 합니다.)

 

 

완전 탐색을 거친 후 중복된 집합을 제거하기 위해, index 가 빠른 순을 기준으로 횟수를 기록하도록 합니다.

위의 두 과정을 거치게 되면, 문제를 해결해 볼 수 있습니다. 

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
[WEEKLYCALENDAR] Weekly Calendar  (0) 2022.01.03
[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
[HAMMINGCODE] Hamming Code  (0) 2021.12.30
Posted by N'

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/CLOCKSYNC

 

algospot.com ::   CLOCKSYNC

Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록

www.algospot.com


이 문제를 풀 수 있는 방법은 2가지가 있습니다.
각각의 방법에 대해 알아보도록 하겠습니다. 🤔

 

 

1. 재귀를 이용한 완전탐색

 

각각의 시계를 0~3회씩 돌려, 가장 적은 수로 시계를 맞춘 경우의 수를 찾습니다.
4회 이상부터는 0회와 동일하기 때문에 해당 경우의 수는 찾지 않습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;
 
public class Main {
    private static final int IMPOSSIBLE = -1;
    private static final int MAX_USE_COUNT = 4;
    private static final int[][] controllers = new int[][] {
            {012},
            {37911},
            {4101415},
            {04567},
            {6781012},
            {021415},
            {31415},
            {4571415},
            {12345},
            {345913}
    };
 
    public static void main(String[] args) {
        int[] states = new int[16];
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            for (int i = 0; i < 16++i) {
                states[i] = scanner.nextInt() % 12;
            }
 
            System.out.println(getMinTimes(states, 00));
        }
    }
 
    private static int getMinTimes(int[] states, int index, int times) {
        if (isComplete(states)) return times;
        if (index >= controllers.lengthreturn IMPOSSIBLE;
        int[] controller = controllers[index];
 
        int ret = IMPOSSIBLE;
        for (int i = 0; i < MAX_USE_COUNT; ++i) {
            int candidate = getMinTimes(states, index + 1, times + i);
            if (ret == IMPOSSIBLE) ret = candidate;
            else if (candidate != IMPOSSIBLE) ret = Math.min(ret, candidate);
 
            for (int controlIndex : controller) states[controlIndex] = (states[controlIndex] + 3) % 12;
        }
 
        return ret;
    }
 
    private static boolean isComplete(int[] states) {
        for (int state : states) if (state != 0return false;
        return true;
    }
}
cs

 

 

 

2. 문제 속 힌트 사용

 

각 시계에 대해 조정할 수 있는 버튼을 나열해보면, 다음과 같습니다.

 

0 : 0, 3, 5
1 : 0, 8
2 : 0, 5, 8
3 : 1, 6, 8, 9
4 : 2, 3, 7, 8, 9
5 : 3, 7, 8, 9
6 : 3, 4
7 : 1, 3, 4, 7
8 : 4,
9 : 1, 9
10 : 2, 4
11 : 1
12 : 4
13 : 9
14 : 2, 5, 6, 7
15 : 2, 5, 6, 7

 

주의깊게 살펴봐야할 부분은 시계를 조정하기 위해 사용할 수 있는 버튼이 오직 1개만 존재하는 경우가 존재하는 것을 확인해볼 수 있습니다.
(11번째 시계는 오직 1번 버튼으로만 조정 가능)

이와 같은 경우에 해당하는 시계부터 하나씩 조정하는 것을 고려하면, 다음의 순서를 나열해볼 수 있습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
private static final int[][] controllerAndBiasClockOrders = new int[][]{
    {111},
    {48},
    {99},
    {210},
    {36},
    {77},
    {84},
    {01},
    {52},
    {30},
    {63}
}
cs

 

위의 배열을 이용하여 1번 버튼을 11번 시계가 먼저 12시가 되도록, 4번 버튼을 8번 시계가 12시가 되도록, 9번 버튼을 9번 시계가 12시가 되도록...... 조정하도록 합니다.

이를 이용한 코드는 다음과 같습니다. 😆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;
 
public class Main {
    private static final int IMPOSSIBLE = -1;
    private static final int MAX_USE_COUNT = 4;
    private static final int[][] controllers = new int[][] {
            {012},
            {37911},
            {4101415},
            {04567},
            {6781012},
            {021415},
            {31415},
            {4571415},
            {12345},
            {345913}
    };
 
    public static void main(String[] args) {
        int[] states = new int[16];
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            for (int i = 0; i < 16++i) {
                states[i] = scanner.nextInt() % 12;
            }
 
            System.out.println(getMinTimes(states, 00));
        }
    }
 
    private static int getMinTimes(int[] states, int index, int times) {
        if (isComplete(states)) return times;
        if (index >= controllers.lengthreturn IMPOSSIBLE;
        int[] controller = controllers[index];
 
        int ret = IMPOSSIBLE;
        for (int i = 0; i < MAX_USE_COUNT; ++i) {
            int candidate = getMinTimes(states, index + 1, times + i);
            if (ret == IMPOSSIBLE) ret = candidate;
            else if (candidate != IMPOSSIBLE) ret = Math.min(ret, candidate);
 
            for (int controlIndex : controller) states[controlIndex] = (states[controlIndex] + 3) % 12;
        }
 
        return ret;
    }
 
    private static boolean isComplete(int[] states) {
        for (int state : states) if (state != 0return false;
        return true;
    }
}
cs


이 방법은 완전 탐색하는 방법이 아닌, 문제의 힌트를 이용해 특정 방법으로만 찾아 처리하기 때문에 속도가 더 빠를 수 있음을 볼 수 있습니다. (4^10회 vs 10 회)
처음에는 시간제한이 10,000 ms 이기 때문에 완전탐색으로 충분히 풀 수 있을 것이라 생각하고 접근을 하게 되었습니다.
그런데 다른 사람들의 처리 시간이 완전 탐색을 했을 때의 시간보다 너무 짧게 나오는 것을 확인하고 다른 방법을 찾아보다 이와 같은 힌트가 있음을 알게되었습니다.

한번 두 가지 방법을 모두 살펴보는 것을 추천드립니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[SHISENSHO] Shisen-sho  (0) 2022.01.03
[WEEKLYCALENDAR] Weekly Calendar  (0) 2022.01.03
[HAMMINGCODE] Hamming Code  (0) 2021.12.30
[WEIRD] Weird Numbers  (0) 2021.12.30
[XHAENEUNG] 째능 교육  (0) 2021.12.29
Posted by N'

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/WEIRD

 

algospot.com :: WEIRD

Weird Numbers 문제 정보 문제 In mathematics, weird numbers are natural numbers that are abundant but not semiperfect. In other words, a natural number N is a weird number if and only if: Sum of its proper divisors (i.e. less than N ) is greater than

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            System.out.println(isWeird(scanner.nextInt()) ? "weird" : "not weird");
        }
    }
    
    private static boolean isWeird(int n) {
        List<Integer> divisors = getDescSortedDivisors(n);
        if (divisors.size() < 2throw new IllegalArgumentException("N was not greater than 1");
        
        return isWeird(divisors.remove(0), divisors);
    }
 
    private static boolean isWeird(int n, List<Integer> divisors) {
        // Condition 1 : Sum of its proper divisors (i.e. less than N ) is greater than the number.
        int sum = 0;
        for (Integer divisor : divisors) {
            sum += divisor;
        }
        if (sum < n) return false;
 
        // Condition 2 : No subset of its divisors sum to N.
        return !hasSumOfDivisorsToN(n, divisors, 00);
    }
 
    private static List<Integer> getDescSortedDivisors(int n) {
        List<Integer> ret = new ArrayList<>();
        for (int i = (int) Math.sqrt(n); i >= 1--i) {
            if (n % i != 0continue;
            int divide = n / i;
            if (divide == i) ret.add(divide);
            else {
                ret.add(0, divide);
                ret.add(i);
            }
        }
 
        return ret;
    }
 
    private static boolean hasSumOfDivisorsToN(int n, List<Integer> divisors, int acc, int cur) {
        if (n == acc) return true;  // 기저사례 1 : 누적된 덧셈이 n 가 동일한가? (N 을 구성할 수 있는 Subset 존재)
        if (n < acc) return false;  // 기저사례 2 : 누적된 덧셈이 n 보다 큰가? (해당 경우의 수는 더 살펴보지 않음)
        if (divisors.size() <= cur) return false// 기저사례 3 : index 가 약수의 개수를 초과 (경우의 수 끝에 도달)
 
        // 각 index 의 숫자를 포함하는 경우와 아닌 경우에 따라 완전탐색을 한다.
        // 큰 수를 먼저 덧셈하기 때문에, 기저사례2 에 먼저 도달할 수 있도록 처리한다.
        return hasSumOfDivisorsToN(n, divisors, acc + divisors.get(cur), cur + 1)
                || hasSumOfDivisorsToN(n, divisors, acc, cur + 1);
    }
}
cs

 


이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
[HAMMINGCODE] Hamming Code  (0) 2021.12.30
[XHAENEUNG] 째능 교육  (0) 2021.12.29
[URI] URI Decoding  (0) 2021.12.29
[BOARDCOVER] 게임판 덮기  (0) 2021.12.28
Posted by N'

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/BOARDCOVER

 

algospot.com :: BOARDCOVER

게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이

www.algospot.com


풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Scanner;
 
public class Main {
    private static final char WHITE = '.';
    private static final char USE = '^';
    /**
     * index 가 빠른 순서를 기준으로 탐색하기 위한 상태좌표 (y, x)
     * 칸을 덮는 부분에 대해 코드로 구현하는 것이 아닌, 데이터로 나타내는 것이 중요하다.
     *
     * (1) **  (2) *   (3) **  (4)  *
     *      *      **      *       **
     */
    private static final int[][][] coverTypes = {
            {{00}, {01}, {11}}, // (1)
            {{00}, {10}, {11}}, // (2)
            {{00}, {10}, {01}}, // (3)
            {{00}, {1-1}, {10}} // (4)
    };
    private static final char[][] boards = new char[20][20];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int h = scanner.nextInt();
            int w = scanner.nextInt();
            for (int i = 0; i < h; ++i) {
                String line = scanner.next();
                for (int j = 0, len = line.length(); j < len; ++j) {
                    boards[i][j] =  line.charAt(j);
                }
            }
 
            System.out.println(getCount(h, w));
        }
    }
 
    private static int getCount(int h, int w) {
        Coordinate start = getStart(h, w);
        if (start == null) {
            // 기저사례 : 시작할 좌표가 없다면, 모든 보드가 채워졌음.
            return 1;
        }
 
        int ret = 0;
        for (int type = 0; type < 4++type) {
            if (isCoverall(h, w, start.y, start.x, type)) {
                cover(start.y, start.x, type, true);
                ret += getCount(h, w);
                cover(start.y, start.x, type, false);
            }
        }
 
        return ret;
    }
 
    private static Coordinate getStart(int h, int w) {
        for (int i = 0; i < h; ++i) {
            for (int j = 0; j < w; ++j) {
                if (boards[i][j] == WHITE) return new Coordinate(i, j);
            }
        }
        return null;
    }
 
    private static boolean isCoverall(int h, int w, int y, int x, int type) {
        for (int i = 0; i < 3++i) {
            int targetY = y + coverTypes[type][i][0], targetX = x + coverTypes[type][i][1];
            if (targetY < 0 || targetY >= h) return false;
            if (targetX < 0 || targetX >= w) return false;
            if (boards[targetY][targetX] != WHITE) return false;
        }
 
        return true;
    }
 
    private static void cover(int y, int x, int type, boolean isCover) {
        for (int i = 0; i < 3++i) {
            boards[y + coverTypes[type][i][0]][x + coverTypes[type][i][1]] = isCover ? USE : WHITE;
        }
    }
 
    private static final class Coordinate {
        final int y, x;
 
        public Coordinate(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }
}
cs


이 풀이는 기존에 풀었던 아래 문제와 유사합니다. 

 

[PICNIC] 피크닉


재귀로 완전 탐색을 하되, 중복 케이스를 세는 것을 방지하기 위해 사전 순을 기준으로 조회하도록 하였습니다.

이번 문제에서 한번 더 주의 깊게 살펴볼 내용은 게임판을 덮는 케이스 4 가지를 배열로 선언했다는 점인데요. 
처음 문제를 풀었을 때는 게임판을 덮는 방법을 코드로 제작하였는데, 각 방법의 변하는 부분인 상대좌표를 배열로 나타낸다면 조금 더 보기 쉬운 코드가 만들어질 수 있음을 알게 되었습니다.

1
2
3
4
5
6
int[][][] coverTypes = {
    {{00}, {01}, {11}}, // (1)
    {{00}, {10}, {11}}, // (2)
    {{00}, {10}, {01}}, // (3)
    {{00}, {1-1}, {10}} // (4)
};
cs



이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[XHAENEUNG] 째능 교육  (0) 2021.12.29
[URI] URI Decoding  (0) 2021.12.29
[HOTSUMMER] 에어컨을 끈다고 전력난이 해결될까?  (0) 2021.12.27
[CONVERT] Conversions  (0) 2021.12.27
[PICNIC] 소풍  (0) 2021.12.27
Posted by N'

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/PICNIC

 

algospot.com :: PICNIC

소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로

www.algospot.com

 

풀이입니다. 🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.*;
 
public class Main {
    // 친구 관계 정의
    // friends[0][1] 이 true 라면, 0 과 1 은 친구.
    private static final boolean[][] friends = new boolean[10][10];
    private static final boolean[] uses = new boolean[10];
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt(), m = scanner.nextInt();
            for (int i = 0; i < m; ++i) {
                int a = scanner.nextInt(), b = scanner.nextInt();
                friends[a][b] = true;
                friends[b][a] = true;
            }
            
            System.out.println(getCombinationCount(n));
            
            Arrays.fill(uses, false);
            for (int i = 0; i < n; ++i) Arrays.fill(friends[i], false);
        }
    }
 
    private static int getCombinationCount(int n) {
        int indexOfNotUses = getMinIndexOfNotUses(n);
        // 기저 사례 : 모든 사람이 사용되었음
        if (indexOfNotUses == -1return 1;
 
        // 작은 수가 큰 수를 선택하는 방식으로 탐색할 가짓수를 줄인다.
        // [1, 3] 과 [3, 1] 은 동일.
        int ret = 0;
        for (int i = indexOfNotUses + 1; i < n; ++i) {
            if (uses[i]) continue;
            if (!friends[indexOfNotUses][i]) continue;
 
            uses[indexOfNotUses] = uses[i] = true;
            ret += getCombinationCount(n);
            uses[indexOfNotUses] = uses[i] = false;
        }
 
        return ret;
    }
 
    private static int getMinIndexOfNotUses(int n) {
        for (int i = 0; i < n; ++i) {
            if (!uses[i]) return i;
        }
 
        return -1;
    }
}
 
cs

 


이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[HOTSUMMER] 에어컨을 끈다고 전력난이 해결될까?  (0) 2021.12.27
[CONVERT] Conversions  (0) 2021.12.27
[ENCRYPT] 문자열 암호화  (0) 2021.12.27
[LECTURE] Lecture Note  (0) 2021.12.27
[DRAWRECT] 사각형 그리기  (0) 2021.12.27
Posted by N'