SW 역량 테스트 기출 문제(경사로, 톱니 바퀴)

[경사로 _ 14890]

 

 

* 조건

1. 행, 열 기준으로 한줄로 이동해나갈 때,
   • 기준점의 높이와 다음 칸의 높이 차이가 1을 초과하면 해당 경로는 지나갈 수 없다
   • 높이 차이가 0이면 평면이기 때문에 그대로 이동
   • 높이 차이가 1이라면
     - 아래에서 위로 경사로를 설치하는 경우
     - 위에서 아래로 경사로를 설치하는 경우
     
     로 나눠야한다
2. 경사로는 설치된 곳에는 다시 설치 불가능하다
3. 경사로의 길이(L)만큼의 공간이 없다면 설치 불가능하다
4. 지나갈 수 있는 경로의 개수를 출력한다

* 알고리즘

- 이동을 하고 경사로를 설치하는 과정을 진행: 시뮬레이션

 

* 로직(Logic)

- 우선 (0,0)을 기준으로 행을 하나씩 이동시켜 경로를 지나갈 수 있는지 확인한다 (ex. (0,0) -> (1,0) -> (2,0) ...)

- 하나씩 움직이면서 현재 좌표의 높이와 움직인 좌표의 높이를 구한다

- 높이의 차를 구하고

-> 높이 차이가 2이상이면 해당 경로는 지나갈 수 없음

-> 높이 차이가 0이면 평면이기 때문에 다음 좌표로 이동이 가능

-> 높이 차이가 1이면 아래에서 위로 설치하는지 or 위에서 아래로 설치하는지의 경우를 나눠준다

 

- 설치를 하는 과정에서 설치된 좌표는 마킹을 해준다 (조건-2)

- 아무런 문제없이 통과된다면 count++

- 열도 마찬가지로 진행한다

 

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

public class Problem_14890 {

    static int N, L;
    static int[][] map;
    static int count = 0;

    //아래, 오른
    static int[] dy = {1, 0};
    static int[] dx = {0, 1};
    static boolean[][] checked;

    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());
        L = Integer.parseInt(st.nextToken());
        map = new int[N][N];

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

        //행의 기준을 한칸씩 늘린 경우
        for(int i=0; i<N; ++i){
            checked = new boolean[N][N];
            int j = 0;
            int dir = 1;
            doProcess(i, j, dir);
        }

        //열의 기준을 한칸씩 늘린 경우
        for(int j=0; j<N; ++j){
            checked = new boolean[N][N];
            int i = 0;
            int dir = 0;
            doProcess(i, j, dir);
        }

        System.out.println(count);
    }

    private static void doProcess(int i, int j, int dir) {

        //사람을 이동시키기 -> 이동시키다가 map의 높이차이가 1을 초과하면 x, 높이차이가 1이면 L의 길이를 고려해 높이가 유지되는지 확인 후 -> 가능하면 L만큼 이동
        if(move(i, j, dir)){
            count++;
        }
    }

    private static boolean move(int i, int j, int dir) {
        while (true){
            int moveY = i + dy[dir];
            int moveX = j + dx[dir];

            if(!isRanged(moveY, moveX)) return true;

            //1을 초과하면 false
            if(Math.abs(map[i][j] - map[moveY][moveX]) > 1){
                return false;
            }

            if(Math.abs(map[i][j] - map[moveY][moveX]) == 0){
                i = moveY;
                j = moveX;
                //continue;
            }

            //높이차이가 1이라면
            else if(Math.abs(map[i][j] - map[moveY][moveX]) == 1){
                int tmpY = 0, tmpX = 0;
                int baseY;
                int baseX;

                //L 길이만큼 경사로를 둘 수 있는지 판별
                //경사로를 위 -> 아래로 설치한다면
                if(map[i][j] > map[moveY][moveX]){
                    baseY = moveY;
                    baseX = moveX;
                    if(checked[baseY][baseX]){
                        return false;
                    }
                    checked[baseY][baseX] = true;

                    for(int a=0; a<L-1; ++a){
                        tmpY = baseY + dy[dir];
                        tmpX = baseX + dx[dir];

                        if(isRanged(tmpY, tmpX)){
                            if(Math.abs(map[baseY][baseX] - map[tmpY][tmpX]) > 0){
                                return false;
                            }
                            //높이가 유지된다면 경사로를 놓은 좌표로 이동
                            else if(Math.abs(map[baseY][baseX] - map[tmpY][tmpX]) == 0){
                                baseY = tmpY;
                                baseX = tmpX;
                                checked[baseY][baseX] = true;
                            }
                        }
                        else return false;
                    }

                    i = baseY;
                    j = baseX;
                }

                //경사로를 아래 -> 위로 설치한다면 -> 이전의 높이가 동일한 좌표들이 L개 있어야함
                else if(map[i][j] < map[moveY][moveX]){
                    baseY = i;
                    baseX = j;
                    if(checked[baseY][baseX]){
                       return false;
                    }
                    checked[baseY][baseX] = true;
                    for(int a=0; a<L-1; ++a){
                        tmpY = baseY - dy[dir];
                        tmpX = baseX - dx[dir];

                        if(isRanged(tmpY, tmpX)){
                            if(checked[tmpY][tmpX]){
                                return false;
                            }

                            if(Math.abs(map[baseY][baseX] - map[tmpY][tmpX]) > 0){
                                return false;
                            }
                            else if(Math.abs(map[baseY][baseX] - map[tmpY][tmpX]) == 0){
                                baseY = tmpY;
                                baseX = tmpX;
                                checked[baseY][baseX] = true;
                            }
                        }
                        else return false;
                    }

                    i = i + dy[dir];
                    j = j + dx[dir];
                }
            }
        }
    }

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

 

[톱니바퀴 _ 14891]

 

 

* 조건

1. 주어진 명령에 맞는 톱니바퀴와 N<->S를 이룬다면 반대방향으로 회전이 가능하다
2. 같은 극을 띈다면 해당 톱니바퀴는 회전이 불가하다
3. 12시 방향의 극이 S이면 점수를 얻을 수 있다

* 알고리즘

- 입력된 명령에 맞게 구현: 시뮬레이션

 

* 로직(Logic)

- 명령을 수행할 해당 톱니를 기준으로 왼쪽, 오른쪽 방향을 탐색하면서 서로 다른 극을 가진다면 인접한 톱니의 회전 가능을 마킹해준다

- 만약 같은 극을 가진다면 마킹을 하지 않는다

- 회전을 실행할 때 역시 명령이 시작될 톱니를 기준으로 왼쪽, 오른쪽으로 탐색을 진행한다

- 만약 회전 가능 마킹이 되어있다면 반대 방향으로 회전이 이루어지도록 한다

- 명령이 모두 끝났다면, 배열 인덱스를 기준으로 맨 처음 인덱스 값이 12시 방향이기 때문에 각 톱니 별로 [0] 인덱스 부분을 누적해서 값을 구한다

 

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

public class Problem_14891 {

    static StringTokenizer st;
    static int size = 8;
    static LinkedList<String>[] gears = new LinkedList[size];

    static int operNum;
    static int operIdx = 0;
    static ArrayList<String> operations = new ArrayList<>();

    static boolean[] checked;   //N<->S이면 해당 톱니바퀴를 마킹
    static boolean leftMark;
    static boolean rightMark;

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

        for(int i=0; i<4; ++i){
            String input = br.readLine();
            gears[i] = new LinkedList<>();
            for(int j=0; j<size; ++j){
                gears[i].add(input.substring(j, j+1));
            }
        }

        //명령 입력
        operNum = Integer.parseInt(br.readLine());
        for(int i=0; i<operNum; ++i){
            String input = br.readLine();
            operations.add(input);
        }

        //명령이 입력된 톱니를 기준으로 왼쪽으로 인접해있는 톱니 && 오른쪽으로 인접해있는 톱니를 탐색
        //(왼쪽)만약 N<->S처럼 되어있다면 해당 톱니를 마킹해주고 -> 해당 톱니의 왼쪽에 인접한 톱니를 다시 탐색 -> 만약 같은 극이라면 종료
        //(오른쪽) 마찬가지로 진행

        //명령이 입력된 톱니를 먼저 돌리고
        //(왼쪽) 마킹이 되어있다면 반대 방향으로 회전시킴 -> 마킹이 없다면 종료
        //(오른쪽)도 마찬가지로 진행
        doProcess();

        int acc = 0;
        int weight = 1;
        for(int i=0; i<4; ++i){
            if(gears[i].get(0).equals("1")){
                acc = acc + weight;
            }
            weight *= 2;
        }

        System.out.println(acc);
    }

    private static void doProcess() {
        for(int i=0; i<operations.size(); ++i){
            String input = operations.get(operIdx++);
            st = new StringTokenizer(input, " ");
            int gearIdx = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());

            checked = new boolean[4];
            checked[gearIdx] = true;
            findInterLock(gearIdx);

            //기준 톱니 회전
            doRotate(gearIdx, dir);

            int leftIdx = gearIdx;
            int rightIdx = gearIdx;
            int leftDir = dir, rightDir = dir;
            leftMark = false;
            rightMark = false;
            while (true){

                if(leftMark && rightMark) {
                    break;
                }
                //왼쪽 방향 회전 적용
                if(!leftMark){
                    leftIdx--;
                    leftDir *= -1;
                    doRotate(leftIdx, leftDir);
                }

                //오른쪽 방향 회전 적용
                if(!rightMark){
                    rightIdx++;
                    rightDir *= -1;
                    doRotate(rightIdx, rightDir);
                }
            }
        }
    }

    private static void doRotate(int gearIdx, int dir) {
        if(gearIdx < 0) {
            leftMark = true;
            return;
        }
        else if(gearIdx >= 4) {
            rightMark = true;
            return;
        }

        if(checked[gearIdx]){
            switch (dir){
                //시계방향 (오른쪽으로 밀어줌)
                case 1:
                    String rear = gears[gearIdx].removeLast();
                    gears[gearIdx].addFirst(rear);
                    break;

                //반시계방향 (왼쪽으로 밀어줌)
                case -1:
                    String front = gears[gearIdx].removeFirst();
                    gears[gearIdx].addLast(front);
                    break;
            }
        }
    }

    private static void findInterLock(int index) {
        //해당 톱니를 기준으로 왼쪽으로 탐색
        findLeft(index);

        //해당 톱니를 기준으로 오른쪽으로 탐색
        findRight(index);
    }

    private static void findRight(int index) {
        while (true){
            int moveIdx = index + 1;
            if(moveIdx >= 4){
                return;
            }

            String current = gears[index].get(2);
            String moved = gears[moveIdx].get(6);
            if(current.equals(moved)){
                return;
            }
            if(!current.equals(moved)){
                checked[moveIdx] = true;
            }
            index = moveIdx;
        }
    }

    private static void findLeft(int index) {
        while (true){
            int moveIdx = index - 1;
            if(moveIdx < 0){
                return;
            }

            String current = gears[index].get(6);
            String moved = gears[moveIdx].get(2);
            if(current.equals(moved)){
                return;
            }
            if(!current.equals(moved)){
                checked[moveIdx] = true;
            }
            index = moveIdx;
        }
    }
}

 

시뮬레이션의 경우 예외 케이스 처리의 중요성을 체감했다. 구현이 다 됐다고 생각이 들더라도, 항상 문제에 주어진 엣지 케이스를 생각하는 습관을 들이면 고생을 덜 할 수 있을 것 같다. 어떤 문제든지 엣지 케이스는 중요하지만 시뮬레이션의 경우 한번 더 생각해보는 습관을 의식적으로라도 해봐야겠다.