☌

[NOTE] Note

개발이야기/알고스팟2022. 1. 6. 10:33

C 로 풀어보는 알고리즘입니다. 📖 

(이번 문제는 Java 를 이용할 시, input 과정 중 시간초과를 발생시키는 요소가 있는 것 같아 보입니다.)
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

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

 

algospot.com :: NOTE

Note 문제 정보 문제 C major scale consists of 8 tones: c d e f g a b C. For this task we number the notes using numbers 1 through 8. The scale can be played ascending, from 1 to 8, descending, from 8 to 1, or mixed. Write a program that, given the se

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
#include <stdio.h>
#define ASC 0
#define DESC 1
#define MIX 2
 
int main()
{
    int oldValue, newValue, ret = MIX;
    for (int i = 0; i < 8; ++i)
    {
        scanf("%d", &newValue);
        if (i == 0)
        {
            if (newValue == 1 || newValue == 8)
            {
                ret = (newValue == 1) ? ASC : DESC;
                oldValue = newValue;
            }
        }
        else
        {
            switch (ret)
            {
            case ASC:
                ret = (newValue - oldValue == 1) ? ASC : MIX;
                break;
 
            case DESC:
                ret = (oldValue - newValue == 1) ? DESC : MIX;
                break;
            }
 
            oldValue = newValue;
        }
    }
 
    switch (ret)
    {
    case ASC:
        printf("ascending\n");
        break;
 
    case DESC:
        printf("descending\n");
        break;
 
    case MIX:
        printf("mixed\n");
        break;
    }
 
    return 0;
}
 cs

 

 

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

반응형

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

[KAKURO1] Kakuro I  (0) 2022.01.06
[FESTIVAL] 록 페스티벌  (0) 2022.01.06
[MAGICPOWER] 마력  (0) 2022.01.05
[DECODE] Decoding  (0) 2022.01.05
[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
Posted by N'
,

[MAGICPOWER] 마력

개발이야기/알고스팟2022. 1. 5. 10:07

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

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

 

algospot.com :: MAGICPOWER

마력 문제 정보 문제 KAIST에는 우리가 모르는 전설의 마법사(!)가 살고 있다. 전설의 마법사는 아이템을 사용해서 마력을 보충하는데, 아이템에 쓰여 있는 수만큼 마력을 얻을 수 있다고 한다. 그

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[] items = new int[100];
 
    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 < n; ++i) items[i] = scanner.nextInt();
 
            int ret = 0;
            while (m-- > 0) {
                int maxIndex = maxIndexOf(n);
                int maxValue = items[maxIndex];
                ret += maxValue;
                items[maxIndex] = Math.max(maxValue - 1, 0);
            }
 
            System.out.println(ret);
        }
    }
 
    private static int maxIndexOf(int n) {
        int ret = 0, max = 0;
        for (int i = 0; i < n; ++i) {
            if (max >= items[i]) continue;
            max = items[i];
            ret = i;
        }
 
        return ret;
    }
}
 cs

 

 

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

반응형

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

[FESTIVAL] 록 페스티벌  (0) 2022.01.06
[NOTE] Note  (0) 2022.01.06
[DECODE] Decoding  (0) 2022.01.05
[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
Posted by N'
,

[DECODE] Decoding

개발이야기/알고스팟2022. 1. 5. 10:03

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

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

 

algospot.com :: DECODE

Decoding 문제 정보 문제 Chip and Dale have devised an encryption method to hide their (written) text messages. They first agree secretly on two numbers that will be used as the number of rows (R) and columns (C) in a matrix. The sender encodes an int

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
import java.util.*;
 
public class Main {
    private static final int USE = -1;
    private static final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
    public static void main(String[] args) {
        int[] acc = new int[5];
        int[][] boards = new int[20][20];
        Scanner scanner = new Scanner(System.in);
 
        int cases = scanner.nextInt();
        for (int i = 1; i <= cases; ++i) {
            int r = scanner.nextInt(), c = scanner.nextInt();
            char[] matrix = scanner.next().toCharArray();
            for (int j = 0, len = matrix.length; j < len; ++j) boards[j / c][j % c] = matrix[j] - '0';
 
            System.out.printf("%d %s\n", i, getDecode(boards, acc, r, c));
        }
    }
 
    private static String getDecode(int[][] boards, int[] acc, int r, int c) {
        StringBuilder builder = new StringBuilder();
        int y = 0, x = 0, accLength = 0, directionIndex = 0;
        do {
            acc[accLength++] = boards[y][x];
            boards[y][x] = USE;
            if (accLength == 5) {
                accLength = 0;
                builder.append(toString(toDecimal(acc)));
            }
 
            if (isMovable(boards, r, c, y, x, directionIndex)
                    || isMovable(boards, r, c, y, x, directionIndex = (directionIndex + 1) % 4)) {
                y += directions[directionIndex][0];
                x += directions[directionIndex][1];
            } else {
                y = x = -1;
            }
        } while (y != -1);
 
        return builder.toString();
    }
 
    private static int toDecimal(int[] acc) {
        return 16 * acc[0] + 8 * acc[1] + 4 * acc[2] + 2 * acc[3] + acc[4];
    }
 
    private static String toString(int decimal) {
        return (decimal == 0) ? " " : String.format("%c",  'A' + (decimal - 1));
    }
 
    private static boolean isMovable(int[][] boards, int r, int c, int y, int x, int directionIndex) {
        int curY = y + directions[directionIndex][0], curX = x + directions[directionIndex][1];
        if (curY < 0) return false;
        if (curY >= r) return false;
        if (curX < 0) return false;
        if (curX >= c) return false;
        return boards[curY][curX] != USE;
    }
}
 cs

 

나선모양으로 이진수를 읽은 뒤, 10진수로 변경 후, 문제에 주어진 방식처럼 문자로 변경하면 해결할 수 있는 문제입니다. 

나선모양으로 변경하기 위해 각 방향에 대한 이동 처리를 코드로 구현한 것이 아닌, 4가지 방향에 대한 상대좌표를 이용하도록 하였습니다.

 

1
    private static final int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 cs

 

 

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

반응형

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

[NOTE] Note  (0) 2022.01.06
[MAGICPOWER] 마력  (0) 2022.01.05
[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
Posted by N'
,

[FIX] 문제 순서는 난이도 순이 아닙니다

개발이야기/알고스팟2022. 1. 5. 09:55

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

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

 

algospot.com :: FIX

문제 순서는 난이도 순이 아닙니다 문제 정보 문제 알고리즘 문제를 푸는 프로그래밍 대회에서, 문제 순서는 난이도와 관계가 없다. 이 문제는 앞에서부터 풀다가 뒤쪽에 있는 쉬운 문제를 놓치

www.algospot.com

 

풀이입니다. 🤔

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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) {
            int n = scanner.nextInt(), count = 0;
            for (int i = 1; i <= n; ++i) if (scanner.nextInt() == i) ++count;
 
            System.out.println(count);
        }
    }
}
 cs

 

 

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

반응형

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

[MAGICPOWER] 마력  (0) 2022.01.05
[DECODE] Decoding  (0) 2022.01.05
[CSBASEBALL] 각본 없는 야구  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[NQUEEN] N-Queen  (0) 2022.01.04
Posted by N'
,

[CSBASEBALL] 각본 없는 야구

개발이야기/알고스팟2022. 1. 5. 09:49

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

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

 

algospot.com :: CSBASEBALL

각본 없는 야구 문제 정보 문제 현재 CS 야구팀과 화나 핀토스(Hwana Pintos)팀의 야구 경기가 진행 중이다. 지금은 CS 야구팀의 공격 상황. 주자는 아무도 없지만 이들은 계속 안타(1루타)를 치기 시

www.algospot.com


풀이입니다. 🤔

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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) {
            int a = scanner.nextInt(), b = scanner.nextInt();
            int diff = b - a;
            System.out.println(diff >= 0 ? 4 + diff : 0);
        }
    }
}
 cs

 


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

반응형

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

[DECODE] Decoding  (0) 2022.01.05
[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[NQUEEN] N-Queen  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
Posted by N'
,

[TSP1] Traveling Salesman Problem 1

개발이야기/알고스팟2022. 1. 4. 17:59

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'
,

[NQUEEN] N-Queen

개발이야기/알고스팟2022. 1. 4. 16:48

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] != 0) continue;
            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'
,

[FIXPAREN] Mismatched Parenthesis

개발이야기/알고스팟2022. 1. 4. 01:51

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

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

 

algospot.com :: FIXPAREN

Mismatched Parenthesis 문제 정보 문제 You are working on a sequence of parentheses. There are four types of parentheses and the symbols used are ( ), { }, [ ], < >. We call '(', '{', '[', and '<' the left parentheses and ')', '}', ']', and '>' the ri

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
import java.util.*;
 
public class Main {
    private static final Map<Character, Character> brackets = new HashMap<>();
    private static final Map<Character, Character> reverseBrackets = new HashMap<>();
 
    static {
        brackets.put('[', ']');
        brackets.put('{', '}');
        brackets.put('(', ')');
        brackets.put('<', '>');
        reverseBrackets.put(']', '[');
        reverseBrackets.put('}', '{');
        reverseBrackets.put(')', '(');
        reverseBrackets.put('>', '<');
    }
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            String line = scanner.next();
            String orders = scanner.next();
            System.out.println(getMatchedBrackets(line, orders.toCharArray()));
        }
    }
 
    private static String getMatchedBrackets(String line, char[] orders) {
        StringBuilder ret = new StringBuilder();
        Stack<String> stack = new Stack<>();
        for (char c : line.toCharArray()) {
            if (brackets.containsKey(c)) stack.push("" + c);
            else {
                String pop = stack.pop();
                char open = maxOf(pop.charAt(0), reverseBrackets.get(c), orders);
                char close = brackets.get(open);
 
                String acc = open + pop.substring(1) + close;
                if (stack.isEmpty()) ret.append(acc);
                else stack.push(stack.pop() + acc);
            }
        }
 
        return ret.toString();
    }
 
    private static char maxOf(char a, char b, char[] orders) {
        int aOrder = 0, bOrder = 0;
        for (int i = 0, len = orders.length; i < len; ++i) {
            char order = orders[i];
            if (order == a) aOrder = i;
            if (order == b) bOrder = i;
        }
 
        return (aOrder <= bOrder) ? a : b;
    }
}
 cs


어려운 문제는 아니지만, 주의해야할 테스트 케이스가 있습니다. 
기본 예제와 더불어 아래 테스트 케이스도 통과하는지 살펴볼 필요가 있습니다. 

 

3
(} {(<[
()([)> <({[
([<>]{})()  // bracket 안에 수평적인 bracket 이 중복으로 존재

 

 

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

반응형

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

[TSP1] Traveling Salesman Problem 1  (0) 2022.01.04
[NQUEEN] N-Queen  (0) 2022.01.04
[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
[SHISENSHO] Shisen-sho  (0) 2022.01.03
[WEEKLYCALENDAR] Weekly Calendar  (0) 2022.01.03
Posted by N'
,

[BRACKETS2] Mismatched Brackets

개발이야기/알고스팟2022. 1. 3. 22:35

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

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

 

algospot.com :: BRACKETS2

Mismatched Brackets 문제 정보 문제 Best White is a mathematics graduate student at T1 University. Recently, he finished writing a paper and he decided to polish it. As he started to read it from the beginning, he realized that some of the formulas ha

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
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Map<Character, Character> brackets = new HashMap<>();
        brackets.put('[', ']');
        brackets.put('{', '}');
        brackets.put('(', ')');
 
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            String line = scanner.next();
            System.out.println(isRight(line, brackets) ? "YES" : "NO");
        }
    }
 
    private static boolean isRight(String line, Map<Character, Character> brackets) {
        Stack<Character> stack = new Stack<>();
        for (char c : line.toCharArray()) {
            if (brackets.containsKey(c)) stack.push(c);
            else {
                if (stack.isEmpty()) return false;
                if (c != brackets.get(stack.pop())) return false;
            }
        }
 
        return stack.isEmpty();
    }
}
 cs

 

 

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

반응형

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

[NQUEEN] N-Queen  (0) 2022.01.04
[FIXPAREN] Mismatched Parenthesis  (0) 2022.01.04
[SHISENSHO] Shisen-sho  (0) 2022.01.03
[WEEKLYCALENDAR] Weekly Calendar  (0) 2022.01.03
[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
Posted by N'
,

[SHISENSHO] Shisen-sho

개발이야기/알고스팟2022. 1. 3. 21:27

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[][]{{-1, 0}, {0, 1}, {1, 0}, {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 == 3) return; // 기저사례 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'
,
Daum / Designed by i2i Labs

티스토리툴바