Problem


수열과 연산자가 주어졌을 때 조합하여 만들수 있는 최소값과 최대값을 구하는 문제입니다.



Solution

연산자가 배치될 수 있는 모든 경우의 수를 구한 후에 MAXMIN 값을 구하는 문제입니다.


단순하게 재귀로 풀수도 있지만 순열을 이용하여 풀었습니다.


모든 경우의 수를 봐야 하고 순서는 중요하지 않기 때문에 간단하게 swap 으로 순열을 구현하였습니다.


  1. operator 배열을 만들어서 각 연산자 갯수에 대해 1, 2, 3, 4로 넣기
  2. operator 배열에 대해서 순열 돌리기
  3. 순열로 인한 경우의 수 마다 연산값을 계산하여 maxmin 값 구하기
  4. 출력


위와 같은 순서로 진행하였습니다.


파이썬은 좀더 예전에 풀었던 거라 연산자를 아예 +, -, *, / 로 배열에 저장했는데 순열을 구한 뒤 계산한다는 전체적인 로직은 같습니다.



Java Code

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

class Main {
    static int n;
    static int[] a;
    static int[] operator;
    static int max = -987654321;
    static int min = 987654321;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = stoi(br.readLine());
        a = new int[n];
        operator = new int[n - 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = stoi(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int idx = 0;
        for (int i = 0; i < 4; i++) {
            int temp = stoi(st.nextToken());

            // 1:덧셈, 2:뺄셈, 3:곱셈, 4:나눗셈
            for (int j = 0; j < temp; j++) {
                if (i == 0) operator[idx++] = 1;
                else if (i == 1) operator[idx++] = 2;
                else if (i == 2) operator[idx++] = 3;
                else operator[idx++] = 4;
            }
        }

        // 계산 시작
        permutation(0);
        System.out.println(max);
        System.out.println(min);
    }

    // 순열 구하기
    static void permutation(int depth) {
        if (depth == n - 1) {
            calculate();
            return;
        }

        for (int i = depth; i < n - 1; i++) {
            swap(depth, i);
            permutation(depth + 1);
            swap(depth, i);
        }
    }

    static void swap(int i, int j) {
        int temp = operator[i];
        operator[i] = operator[j];
        operator[j] = temp;
    }

    // 각 순열에 대해서 연산 후 max, min 값 찾기
    static void calculate() {
        int result = a[0];

        for (int i = 0; i < n - 1; i++) {
            if (operator[i] == 1) result += a[i + 1];
            else if (operator[i] == 2) result -= a[i + 1];
            else if (operator[i] == 3) result *= a[i + 1];
            else result /= a[i + 1];
        }

        min = Math.min(min, result);
        max = Math.max(max, result);
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
def setOperatorList(N, add, sub, mul, div):
    operator = []
 
    for i in range(N-1):
        if add > 0:
            operator.append("+")
            add -= 1
        elif sub > 0:
            operator.append("-")
            sub -= 1
        elif mul > 0:
            operator.append("*")
            mul -= 1
        elif div > 0:
            operator.append("/")
            div -= 1
 
    return operator
 
 
def solve(N, A, operator):
    result = A[0]
 
    for i in range(N-1):
        if operator[i] == "+":
            result = result + A[i+1]
        elif operator[i] == "-":
            result = result - A[i+1]
        elif operator[i] == "*":
            result = result * A[i+1]
        elif operator[i] == "/":
            result = int(result / A[i+1])
 
    return result
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    A = [i for i in list(map(int, sys.stdin.readline().split()))]
    add, sub, mul, div = map(int, sys.stdin.readline().split())
    
    operatorList = setOperatorList(N, add, sub, mul, div)
 
    operators = itertools.permutations(operatorList)
 
    maxVal = -sys.maxsize
    minVal = sys.maxsize
 
    for operator in operators:
        result = solve(N, A, operator)
 
        if result < minVal:
            minVal = result
        
        if result > maxVal:
            maxVal = result
 
    print(maxVal)
    print(minVal)


문제 링크 : https://www.acmicpc.net/problem/1182


부분집합을 이용하는 문제입니다.


부분집합에 대한 이전 포스팅 https://bcp0109.tistory.com/17


원소를 일일히 기억할 필요가 없어서 코드가 훨씬 간단해집니다.


배열 인덱스의 처음부터 끝까지 진행하며


1) arr[idx] 값을 더한 경우

2) arr[idx] 값을 더하지 않은 경우


두 가지 경우로 나누어서 탐색합니다.


인덱스의 끝에 도달하면 지금까지 더한 값과 S 를 비교하여 일치할 경우 count++ 해주시면 됩니다.



** 주의사항 **


부분집합을 구하다보면 공집합이 생깁니다.


만약 S 가 0 이라면 공집합때문에 아무 값도 더하지 않아서 0 인 경우도 카운트 하게 됩니다.


이 부분에 대해서만 예외처리를 해주시면 됩니다.


파이썬에서는 조합에 대한 라이브러리를 제공해주기 때문에 그냥 n번만큼 조합을 돌렸습니다.


부분집합


배열의 모든 부분집합을 구합니다.


배열 [1, 2, 3] 이 있다면 부분집합은


[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]

입니다.


뭔가 떠오르지 않나요?


바로 조합이 떠오릅니다.


저번에 포스팅했던 n 개 중에서 r 개를 순서 없이 뽑는 조합에서 r 에 대한 for 문을 돌리면 구할 수 있습니다.


하지만 단순히 부분집합을 확인하기 위한 용도라면 훨씬 빠르고 효율적인 코드가 있습니다.


부분집합 역시 구하는 방법이 여러가지 있습니다.




조합을 이용한 구현

조합  포스팅을 확인하시면 됩니다.




재귀를 이용한 구현

조합을 구할 때와 비슷하게 구현을 하면 됩니다.


조합에서는 길이가 r 일 때를 구하기 위해 여러가지 조건을 걸었지만 부분집합에서는 필요없습니다.

  1. 현재 인덱스를 포함하는 경우
  2. 현재 인덱스를 포함하지 않는 경우

두 가지로 경우에 대해서 모두 확인한 후에 현재 인덱스가 n 이 되면 출력합니다.



Java Code

static void powerSet(int[] arr, boolean[] visited, int n, int idx) {
    if(idx == n) {
        print(arr, visited, n);
        return;
    }
 
    visited[idx] = false;
    powerSet(arr, visited, n, idx + 1);
 
    visited[idx] = true;
    powerSet(arr, visited, n, idx + 1);
}


Result

3
2
2 3
1
1 3
1 2
1 2 3




비트를 이용한 구현

비트연산에 대한 이해가 있다면 구현할 수 있습니다.


n 이 3이라고 할 때 1 << n 은 1000(2) 입니다.


첫번째 for 문에서 i 는 1 << n 전까지 증가하니까 111(2) 까지 증가합니다.


즉 i 


000
001
010
011
100
101
110
111

이렇게 증가합니다.


한번 쓱 보니 비트 자체만으로도 부분 집합이 형성되었습니다.


j 를 통해서

001
010
100

위 숫자들과 AND 연산을 통해서 1 인 비트들을 인덱스처럼 사용할 수 있습니다.



Java Code

static void bit(int[] arr, int n) {
    for(int i=0; i < 1<<n; i++) {
        for(int j=0; j<n; j++) {
            if((i & 1<<j) != 0) 
                System.out.print(arr[j] + " ");
        }
        System.out.println();
    }
}


Result

1
2
1 2
3
1 3
2 3
1 2 3




전체 소스코드

public class PowerSet {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        int n = 3;
        boolean[] visited = new boolean[n];

        powerSet(arr, visited, n, 0);
        bit(arr, n);
    }

    static void powerSet(int[] arr, boolean[] visited, int n, int idx) {
        if (idx == n) {
            print(arr, visited, n);
            return;
        }

        visited[idx] = false;
        powerSet(arr, visited, n, idx + 1);

        visited[idx] = true;
        powerSet(arr, visited, n, idx + 1);
    }

    static void bit(int[] arr, int n) {
        for (int i = 0; i < 1 << n; i++) {
            for (int j = 0; j < n; j++) {
                if ((i & 1 << j) != 0)
                    System.out.print(arr[j] + " ");
            }
            System.out.println();
        }
    }

    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i] == true)
                System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
조합 Combination (Java)  (7) 2018.12.27
순열 Permutation (Java)  (11) 2018.12.27

Problem


일곱 난쟁이의 키가 주어졌을 때 합이 100 이 되도록 하는 일곱 난쟁이의 키를 출력하는 문제입니다.



Solution

문제를 살펴보면 일곱명의 합을 전부 다 구해봐야 할 것 같지만 사실은 두명만 구하면 됩니다.


주어진 난쟁이는 9명, 실제 난쟁이는 7명입니다.


9명 중에서 2명의 키를 뺀 값이 100이기 때문에


2명의 합 = 9명의 합 - 100


위 식을 이루는 2명을 구하면 됩니다.


2명의 합을 O(n) 에 구하는 방법은 정렬 후에 양 끝 인덱스부터 차례로 합을 구해서 비교하면 됩니다.


두 값의 합이 target 보다 작다면 왼쪽 인덱스를 하나 증가시키고, target 보다 크다면 오른쪽 인덱스를 하나 감소시킵니다.



Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] height = new int[9];
        int sum = 0;

        for (int i=0; i<9; i++) {
            int input = Integer.parseInt(br.readLine());
            height[i] = input;
            sum += input;
        }

        Arrays.sort(height);

        eraseTwoHeight(height, sum - 100);

        for (int i=0; i<9; i++) {
            if (height[i] != 0) {
                bw.write(height[i] + "\n");
            }
        }
        bw.flush();
    }

    static void eraseTwoHeight(int[] arr, int target) {
        int left = 0;
        int right = 8;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                arr[left] = 0;
                arr[right] = 0;
                return;
            }
            
            if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
    }
}


조합


조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말합니다.

예를 들어 [1, 2, 3] 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면

[1, 2]
[1, 3]
[2, 3]

이렇게 3 개가 나옵니다.

순열을 뽑았을 때 나오는 [2, 1] [3, 1] [3, 2] 등은 중복이라서 제거됩니다.

부분 집합처럼 이해하시면 됩니다.

여러 가지 방법이 있지만 핵심은 하나입니다.

배열을 처음부터 마지막까지 돌며

  1. 현재 인덱스를 선택하는 경우
  2. 현재 인덱스를 선택하지 않는 경우

이렇게 두가지로 모든 경우를 완전탐색 해주시면 됩니다.


변수설명
arr조합을 뽑아낼 배열
output조합에 뽑혔는지 체크하는 배열
n배열의 길이
r조합의 길이


순열과 달리 조합은 r 을 유지할 필요가 없으므로 숫자를 하나 뽑을때마다 r 을 하나씩 줄여줍니다.

r == 0 일 때가 r 개의 숫자를 뽑은 경우입니다.


백트래킹 이용하여 구현

start 변수는 기준입니다.

start 인덱스를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start 보다 크면 뽑을 후보가 됩니다.

예를 들어 [1, 2, 3] 배열이 있고 start 가 0 부터 시작합니다.

함수에 들어오면 먼저 i 가 start 부터 시작하는 for 문에 들어갑니다.

만약 0 인덱스인 1을 뽑는다면 visited[i] 는 true 가 되고 뽑지 않는다면 visited[i] 는 false 입니다.

1을 선택한 경우와 선택하지 않은 경우 둘 다 봐야합니다.

하지만 더이상 1은 고려 대상이 아니기 때문에 다음 for 문은 무조건 i+1 부터 시작해주어야 합니다.


Java Code

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
        visited[i] = true;
        combination(arr, visited, i + 1, n, r - 1);
        visited[i] = false;
    }
}


Result

[4 개 중에서 1 개 뽑기]
1
2
3
4

[4 개 중에서 2 개 뽑기]
1 2
1 3
1 4
2 3
2 4
3 4

[4 개 중에서 3 개 뽑기]
1 2 3
1 2 4
1 3 4
2 3 4

[4 개 중에서 4 개 뽑기]
1 2 3 4



재귀 이용하여 구현

depth 변수를 사용합니다.

depth 변수는 현재 인덱스라고 생각하면 됩니다.

현재 인덱스를 뽑는다면 visited[depth] = true

뽑지 않는다면 visited[depth] = false

이렇게 진행하면 됩니다.

역시 마찬가지로 뽑은 경우와 뽑지 않은 경우 모두 봐야하고, 그 때 이전에 본 값들은 더이상 고려 대상이 아니기 때문에 depth 은 무조건 1 씩 증가합니다.

depth == n 이 되면 모든 인덱스를 다 보았으므로 재귀를 종료합니다.


Java Code

// 재귀 사용
// 사용 예시 : comb(arr, visited, 0, n, r)
static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
    if (r == 0) {
        print(arr, visited, n);
        return;
    }

    if (depth == n) {
        return;
    }

    visited[depth] = true;
    comb(arr, visited, depth + 1, n, r - 1);

    visited[depth] = false;
    comb(arr, visited, depth + 1, n, r);
}


Result

[4 개 중에서 1 개 뽑기]
1
2
3
4

[4 개 중에서 2 개 뽑기]
1 2
1 3
1 4
2 3
2 4
3 4

[4 개 중에서 3 개 뽑기]
1 2 3
1 2 4
1 3 4
2 3 4

[4 개 중에서 4 개 뽑기]
1 2 3 4


저는 개인적으로 재귀를 별로 좋아하지 않아서 백트래킹 방법을 주로 사용하는 편입니다.

어느 쪽이든 성능차이가 거의 없으니 편하고 익숙한 방법을 사용하시면 됩니다.



전체 소스코드

/**
 * 조합 : n 개 중에서 r 개 선택
 */
public class Combination {
    public static void main(String[] args) {
        int n = 4;
        int[] arr = {1, 2, 3, 4};
        boolean[] visited = new boolean[n];

        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            comb(arr, visited, 0, n, i);
        }

        for (int i = 1; i <= n; i++) {
            System.out.println("\n" + n + " 개 중에서 " + i + " 개 뽑기");
            combination(arr, visited, 0, n, i);
        }
    }

    // 백트래킹 사용
    // 사용 예시 : combination(arr, visited, 0, n, r)
    static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }

        for (int i = start; i < n; i++) {
            visited[i] = true;
            combination(arr, visited, i + 1, n, r - 1);
            visited[i] = false;
        }
    }

    // 재귀 사용
    // 사용 예시 : comb(arr, visited, 0, n, r)
    static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
        if (r == 0) {
            print(arr, visited, n);
            return;
        }
        
        if (depth == n) {
            return;
        }

        visited[depth] = true;
        comb(arr, visited, depth + 1, n, r - 1);

        visited[depth] = false;
        comb(arr, visited, depth + 1, n, r);
    }

    // 배열 출력
    static void print(int[] arr, boolean[] visited, int n) {
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                System.out.print(arr[i] + " ");
            }
        }
        System.out.println();
    }
}




2차원 배열에서 조합

2차원 배열에서 조합을 뽑아야 할 때가 있어서 만들어보았습니다.


Java Code

/**
 * 2차원 배열에서 조합을 구할때 사용하는 방법
 * 완전 탐색 할때 사용
 */

public class Combination2 {
    static int n = 3;
    static int m = 3;

    public static void main(String[] args) {
        int[][] map = new int[n][m];

        print(map);
        comb(map, 0, 0);
    }

    static void comb(int[][] map, int start, int depth) {
        if (depth == 3) {
            print(map);
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (map[x][y] == 0) {
                map[x][y] = 1;
                comb(map, i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }

    static void print(int[][] map) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27
순열 Permutation (Java)  (11) 2018.12.27

순열


순열이란 n 개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 경우를 말합니다.


예를 들어 [1, 2, 3] 이라는 3 개의 배열에서 2 개의 숫자를 뽑는 경우는


[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

이렇게 6 개가 됩니다.




1. Swap 을 이용한 순열

첫번째는 swap 함수를 만들어서 배열들의 값을 직접 바꾸는 방법입니다.


배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 합니다.


depth 를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고


depth 보다 인덱스가 큰 값들만 가지고 다시 swap 을 진행합니다.



example1



간단하고 코드도 깔끔하게 나오지만 순열들의 순서가 보장되지 않습니다.


예를 들어 3개의 숫자 중 3개의 값을 뽑는 순열을 만들 때


[3, 1, 2]
[3, 2, 1]

위 순서대로 나와야 하는데


[3, 2, 1]
[3, 1, 2]

이렇게 나옵니다.



Java Code

// 순서 없이 n 개중에서 r 개를 뽑는 경우
// 사용 예시: permutation(arr, 0, n, 4);
static void permutation(int[] arr, int depth, int n, int r) {
    if (depth == r) {
        print(arr, r);
        return;
    }
 
    for (int i=depth; i<n; i++) {
        swap(arr, depth, i);
        permutation(arr, depth + 1, n, r);
        swap(arr, depth, i);
    }
}
 
static void swap(int[] arr, int depth, int i) {
    int temp = arr[depth];
    arr[depth] = arr[i];
    arr[i] = temp;
}


Result

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2




2. Visited 배열을 이용한 순열

두번째로는 visited 배열을 이용하는 방법입니다.


1번과 달리 사전식으로 순열을 구현할 수 있습니다.


변수설명
arrr 개를 뽑기 위한 n 개의 값
output뽑힌 r 개의 값
visited중복해서 뽑지 않기 위해 체크하는 값


위 3개의 값이 포인트입니다.


DFS를 돌면서 모든 인덱스를 방문하여 output 에 값을 넣습니다.


이미 들어간 값은 visited 값을 true 로 바꾸어 중복하여 넣지 않도록 합니다.


depth 값은 output 에 들어간 숫자의 길이라고 생각하시면 됩니다.


depth 의 값이 r 만큼 되면 output 에 들어있는 값을 출력하면 됩니다.



example2



Java Code

// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// 사용 예시: perm(arr, output, visited, 0, n, 3);
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
    if (depth == r) {
        print(output, r);
        return;
    }
 
    for (int i=0; i<n; i++) {
        if (visited[i] != true) {
            visited[i] = true;
            output[depth] = arr[i];
            perm(arr, output, visited, depth + 1, n, r);       
            output[depth] = 0; // 이 줄은 없어도 됨
            visited[i] = false;;
        }
    }
}


Result

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1




전체 소스코드

/** * 순열 : n 개 중에서 r 개를 순서있게 뽑기 * 시간복잡도: O(n!) */ public class Permutation { public static void main(String[] args) { int n = 3; int[] arr = {1, 2, 3}; int[] output = new int[n]; boolean[] visited = new boolean[n]; perm(arr, output, visited, 0, n, 3); System.out.println(); permutation(arr, 0, n, 3); } // 사전순으로 순열 구하기 // 사용 예시: perm(arr, output, visited, 0, n, 3); static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) { if (depth == r) { print(output, r); return; } for (int i = 0; i < n; i++) { if (visited[i] != true) { visited[i] = true; output[depth] = arr[i]; perm(arr, output, visited, depth + 1, n, r); visited[i] = false; } } } // 순열 구하기 // 사용 예시: permutation(arr, 0, n, 4); static void permutation(int[] arr, int depth, int n, int r) { if (depth == r) { print(arr, r); return; } for (int i = depth; i < n; i++) { swap(arr, depth, i); permutation(arr, depth + 1, n, r); swap(arr, depth, i); } } static void swap(int[] arr, int depth, int i) { int temp = arr[depth]; arr[depth] = arr[i]; arr[i] = temp; } // 배열 출력 static void print(int[] arr, int r) { for (int i = 0; i < r; i++) System.out.print(arr[i] + " "); System.out.println(); } }


'알고리즘 문제 > 공부' 카테고리의 다른 글

자바 출력 (Java)  (0) 2019.01.05
자바 입력 (Java)  (0) 2019.01.05
위상정렬 Topological Sort (Java)  (1) 2018.12.28
부분집합 PowerSet (Java)  (2) 2018.12.27
조합 Combination (Java)  (7) 2018.12.27

문제 링크 : https://www.acmicpc.net/problem/10974


N 을 입력받아 순열을 출력하는 프로그램입니다.


사전 순으로 출력해야하기 때문에  swap 을 이용한 순열 대신 visited 배열로 방문을 체크하는 DFS 방법을 사용하였습니다.


순열에 대한 이전 포스팅 https://bcp0109.tistory.com/14


arr : 순열을 만들 배열

output : 순열을 만든 후 배열

visited : 방문 체크

depth : dfs 깊이


이렇게 4개의 값을 사용하였고, n개중에서 r개를 뽑는 순열을 구현하였습니다.


문제에서 원하는건 n개 중 n개를 뽑는 경우밖에 없으므로 nPn 만 하시면 됩니다.


Problem


문제에서 시키는 대로 주사위를 굴리는 문제입니다.



Solution

특별한 알고리즘은 없고 문제에서 제시한 대로 구현만 해주면 됩니다.


언뜻 보면 굉장히 복잡한 것 같지만 주사위가 동, 서, 남, 북으로 이동하는 부분만 하드코딩 해주면 간단하게 풀립니다.


저는 Dice라는 클래스를 만들어서 주사위 6면의 값을 저장했습니다.


방향은 동쪽은 1, 서쪽은 2, 북쪽은 3, 남쪽은 4기 때문에 dxdy 배열을 만들때 저 순서대로 만든 후에 1씩 빼주면 됩니다.


함정에 빠질만한 부분이라면 지도의 값이 0이 아닐때 주사위 바닥에 복사를 하는데, 복사 하고 나면 지도값은 0이 되는겁니다.


순서는 문제에 나와있는 대로


  1. 입력받은 방향만큼 for
  2. 움직인 이후의 값이 지도를 벗어나는지 확인
  3. 주사위 이동
  4. 숫자 복사
  5. 맨 윗면 출력


이 순서대로 k번만큼 진행하면 됩니다.


주사위를 이동시킬 때 자바는 temp 값을 사용했지만 파이썬은


x, y = y, x


이렇게 두개의 값을 바꿀수 있다는 특성을 이용하여 구현할 수 있습니다.



Java Code

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

class Main {
    static class Dice {
        int top, bottom, west, east, south, north;

        public Dice() {
            this.top = 0;
            this.bottom = 0;
            this.west = 0;
            this.east = 0;
            this.south = 0;
            this.north = 0;
        }

        public void moveEast() {
            int temp = top;
            top = west;
            west = bottom;
            bottom = east;
            east = temp;
        }

        public void moveWest() {
            int temp = top;
            top = east;
            east = bottom;
            bottom = west;
            west = temp;
        }

        public void moveSouth() {
            int temp = top;
            top = north;
            north = bottom;
            bottom = south;
            south = temp;
        }

        public void moveNorth() {
            int temp = top;
            top = south;
            south = bottom;
            bottom = north;
            north = temp;
        }

        public void printTopNumber() {
            System.out.println(top);
        }
    }

    static int n, m, x, y, k;
    static int[][] map;
    static int[] dir;
    static int[] dx = {0, 0, -1, 1};    // 동서북남
    static int[] dy = {1, -1, 0, 0};

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        x = stoi(st.nextToken());
        y = stoi(st.nextToken());
        k = stoi(st.nextToken());
        map = new int[n][m];
        dir = new int[k];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = stoi(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < k; i++) {
            dir[i] = stoi(st.nextToken());
        }

        solution();
    }

    static void solution() {
        Dice dice = new Dice();
        int nx, ny;

        for (int i = 0; i < k; i++) {
            int direction = dir[i] - 1;
            nx = x + dx[direction];
            ny = y + dy[direction];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                // 동쪽은 0, 서쪽은 1, 북쪽은 2, 남쪽은 3
                if (direction == 0) dice.moveEast();
                else if (direction == 1) dice.moveWest();
                else if (direction == 2) dice.moveNorth();
                else if (direction == 3) dice.moveSouth();

                // 숫자 복사
                if (map[nx][ny] == 0)
                    map[nx][ny] = dice.bottom;
                else {
                    dice.bottom = map[nx][ny];
                    map[nx][ny] = 0;
                }

                // 맨 윗면 출력
                dice.printTopNumber();

                x = nx;
                y = ny;
            }
        }
    }
}



Python Code

# -*- coding: utf-8 -*-
 
import sys
 
N = M = K = 0
arr = []
## 동 서 북 남
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
 
## x, y 좌표와 주사위 상단/하단/동/서/남/북 면에 있는 숫자
class Dice:
    def __init__(self, x, y, top, bottom, e, w, n, s):
        self.x = x
        self.y = y
        self.top = top
        self.bottom = bottom
        self.e = e
        self.w = w
        self.n = n
        self.s = s
 
def move(dice, d):
    nx = dice.x + dx[d]
    ny = dice.y + dy[d]
 
    ## 지도 밖으로 안나가야 됨
    if 0 <= nx and nx < N and 0 <= ny and ny < M:
        dice.x = nx
        dice.y = ny
 
        ## 동 서 북 남
        if d == 0:
            dice.top, dice.bottom, dice.w, dice.e = dice.w, dice.e, dice.bottom, dice.top
        elif d == 1:
            dice.top, dice.bottom, dice.w, dice.e = dice.e, dice.w, dice.top, dice.bottom
            pass
        elif d == 2:
            dice.top, dice.bottom, dice.n, dice.s = dice.s, dice.n, dice.top, dice.bottom
        elif d == 3:
            dice.top, dice.bottom, dice.n, dice.s = dice.n, dice.s, dice.bottom, dice.top
 
        ## 이동한 칸이 0이면 주사위 바닥면 복사
        ## 이동한 칸이 0이 아니면 주사위 바닥면에 숫자 복사하고 칸은 0
        if arr[dice.x][dice.y] == 0:
            arr[dice.x][dice.y] = dice.bottom
        else:
            dice.bottom = arr[dice.x][dice.y]
            arr[dice.x][dice.y] = 0
    else:
        return False
 
    return True
 
def solve(x, y, directions):
    dice = Dice(x, y, 0, 0, 0, 0, 0, 0)
 
    for direction in directions:
        if move(dice, direction-1) == True:
            print(dice.top)
 
if __name__ == '__main__':
    N, M, x, y, K = map(int, sys.stdin.readline().split())
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    directions = list(map(int, sys.stdin.readline().split()))
 
    solve(x, y, directions)


+ Recent posts