SW 역량 테스트 기출 문제(주사위 굴리기, 테트로미노)

[주사위 굴리기 _ 14499]

 

 

* 조건

1. 동서남북(1,2,3,4)
2. 주어진 주사위 전개도를 기준으로 굴리는 상황 고려
3. 맨 처음 주사위의 각 면에는 0으로 초기화
4. 이동한 칸에 0이 아닌 수가 존재 -> 주사위 밑면 = 해당 좌표 값 && 해당 좌표 값 = 0
   0이라면 -> 해당 값 = 주사위 밑면
5. 주사위가 굴러가야 count++
6. 범위를 벗어나면 굴리면 안됨

 

* 알고리즘

- 명령에 맞게끔 작업이 진행: 시뮬레이션

 

* 로직(Logic)

- 기존에 주어진 주사위 각 면에 할당된 번호를 주사위 배열(Dice)의 인덱스라고 생각한다

- 동서남북 방향으로 각가 굴렸을 때 변경되는 인덱스를 미리 배치

- 변경된 각 면의 번호(인덱스)에 존재하는 값을 기존 Dice에 덮어준다

   

- 이동할 좌표가 범위를 벗어난다면 다시 이전 좌표로 큐에 삽입

- 벗어나지 않는다면 해당 방향으로 굴려진 상태로 주사위 값을 변경

- 해당 좌표 값이 0인지 아닌지에 맞게끔 처리

 

 

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

class Position_14499 {
    public int y, x;

    public Position_14499(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Problem_14499 {

    static int n, m, operationNum;
    static int[][] map;

    static Queue<Position_14499> queue = new LinkedList<>();    //주사위의 위치 좌표
    static int[] dice;
    static int[][] crafts_dir = {
            //굴리는 경우(동, 서, 북, 남)
            {2, 1, 5, 0, 4, 3},
            {3, 1, 0, 5, 4, 2},
            {1, 5, 2, 3, 0, 4},
            {4, 0, 2, 3, 5, 1}
    };

    //동 서 북 남
    static int[] dy = {0, 0, -1, 1};
    static int[] dx = {1, -1, 0, 0};

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

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        dice = new int[6];

        //주사위 초기 좌표 큐에 삽입
        int y = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());
        queue.offer(new Position_14499(y,x));

        //명령어 개수 입력
        operationNum = Integer.parseInt(st.nextToken());

        //map 설정
        for(int i=0; i<n; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=0; j<m; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        String input = br.readLine();
        st = new StringTokenizer(input, " ");
        while (st.hasMoreTokens()){
            int dir = Integer.parseInt(st.nextToken());

            //전개도에 부여된 번호를 배열의 인덱스로 관리하고, 4방향으로 굴릴 때의 경우를 적용
            Position_14499 q = queue.poll();
            int moveY = q.y + dy[dir-1];
            int moveX = q.x + dx[dir-1];

            //범위에 벗어나면 기존 위치로 돌아감
            if(moveY<0 || moveY>=n || moveX<0 || moveX>=m){
                queue.offer(new Position_14499(q.y, q.x));
            }

            //아니라면 logic 수행
            else {
                int[] tmp = dice.clone();
                for(int i=0; i<6; ++i){
                    dice[i] = tmp[crafts_dir[dir-1][i]];
                }

                //주사위를 움직이고 윗면 출력
                moveDice(moveY, moveX, q);
                System.out.println(dice[5]);
            }
        }

    }

    private static void moveDice(int moveY, int moveX, Position_14499 q) {

        //해당 지도의 값이 0이면 -> 값 = 주사위 밑면
        if(map[moveY][moveX] == 0) map[moveY][moveX] = dice[0];

        //값이 0아니면 -> 주사위 밑면 = 값 && 값 = 0
        else{
            dice[0] = map[moveY][moveX];
            map[moveY][moveX] = 0;
        }
        queue.offer(new Position_14499(moveY, moveX));

        return;
    }
}

 

[테트로미노 _ 14500]

 

 

* 조건

1. 4개의 칸이 연결된 상태로 위에서 주어진 도형을 만들어내는 최대값을 구해야한다
2. 4칸 이상은 만들 수 없다

* 알고리즘

- (0,0)부터 시작해서 위의 모양을 만들어내는 모든 경우의 수를 구해야 함: 브루트포스

 

* 로직(Logic)

- 우선 DFS를 통해 'ㅗ' 모양을 제외한 모든 모양의 경우를 구할 수 있다 (4칸이 되면 작업 중단, 마킹도 다시 풀어준다)

- 나머지 모양을 처리하기 위해서는 해당 좌표를 기점으로 BFS를 상하좌우로 한번 적용해주면 된다

- if) 인접한 블록의 개수가
    2개 이하: 'ㅗ' 모양을 만들 수 없다

    3개: 기준점을 포함한 인접한 블록과의 합이 곧 값이다

    4개: 십자가가 형성되기 때문에, 인접한 블록들 중 최솟값을 찾고 -> 누적된 합 - 최솟값이 곧 값이다

- 최댓값을 비교하여 답을 출력한다

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Problem_14500 {

    static int[][] map;
    static boolean[][] checked;
    static int n, m;

    static int[] dy = {-1, 0 ,1, 0};
    static int[] dx = {0, 1 ,0, -1};

    static final int CNT = 4;
    static int answer = 0;

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

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for(int i=0; i<n; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=0; j<m; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        checked = new boolean[n][m];
        for(int i=0; i<n; ++i){
            for(int j=0; j<m; ++j){
                int count = 1;
                doProcess(i, j, map[i][j], count);
                doException(i, j, map[i][j]);
            }
        }
        System.out.println(answer);
    }

    private static void doException(int y, int x, int acc) {
        int total = acc;
        int min = Integer.MAX_VALUE;
        int cnt = 0;
        for(int i=0; i<4; ++i){
            int moveY = y + dy[i];
            int moveX = x + dx[i];

            if(isRanged(moveY, moveX)){
                total += map[moveY][moveX];
                min = Math.min(min, map[moveY][moveX]);
                cnt++;
            }
        }
        if(cnt == 3) answer = Math.max(answer, total);
        else if(cnt == 4) answer = Math.max(answer, total-min);
    }

    private static void doProcess(int y, int x, int acc, int count) {
        checked[y][x] = true;
        if(count == CNT){
            answer = Math.max(answer, acc);
            checked[y][x] = false;
            return;
        }

        for(int i=0; i<4; ++i){
            int moveY = y + dy[i];
            int moveX = x + dx[i];

            if(isRanged(moveY, moveX) && !checked[moveY][moveX]){
                doProcess(moveY, moveX, acc + map[moveY][moveX], count+1);
            }
        }
        checked[y][x] = false;
    }

    private static boolean isRanged(int y, int x) {
        if(y>=0 && y<n && x>=0 && x<m) return true;
        return false;
    }
}

 

문제에서 주어진 숫자들을 가지고 배열 인덱스로 접근해보려는 방식의 중요성을 느꼈고, 어느정도의 규칙이 존재한다면 미리 전역으로 설정해놓고 인덱스를 가지고 풀어나가는 연습의 필요성을 체감했다.