SW 역량 테스트 기출 문제(퇴사, 연구소)

[퇴사 _ 14501]

 

 

* 조건

1. 퇴사 날짜 전까지는 스케줄을 진행할 수 있다
2. 수행한 스케줄이 있으면 일당을 받는다
3. 최대로 얻을 수 있는 이익을 구해야한다

* 알고리즘

- 가능한 모든 경우의 수를 탐색: 브루트포스

 

* 로직(Logic)

- 해당 스케줄을 포함하는 경우와 포함하지 않고 다음날의 스케줄을 고려하는 경우를 재귀로 반복 -> 전체 경우 탐색

- 다음 일정이 퇴사일을 넘어가게 되면 -> 이전까지 누적된 이익으로 비교

 

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

public class Problem_14501 {

    static int retireDay;
    static int[] scheduleTime;
    static int[] schedulePrice;

    static int profit = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        retireDay = Integer.parseInt(br.readLine());
        scheduleTime = new int[retireDay];
        schedulePrice = new int[retireDay];

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

        //logic
        int start = 0, price = 0;
        doProcess(start, price);

        System.out.println(profit);
    }


    /*
     * 1) 해당 일에 상담 진행 -> index + scheduleTime[index] <= day 이면 스케줄 가능
     * 2) 해당 일에 상담 진행 x -> index + 1을 통해 다음 날 진행하도록, index+1 <= retireDay 이면 스케줄 가능
     * 재귀를 통해 모든 경우의 수 고려
     * */
    private static void doProcess(int index, int price) {

        if(index >= retireDay){
            profit = Math.max(profit, price);
            return;
        }

        //해당 일을 포함한 경우
        if(index + scheduleTime[index] <= retireDay)
            doProcess(index + scheduleTime[index], price + schedulePrice[index]);

        //포함하지 않고 다음날 스케줄 하는 경우
        if(index+1 <= retireDay)
            doProcess(index+1, price);
    }
}

 

[연구소 _ 14502]

 

 

* 조건

1. 빈칸('0'), 벽('1'), 바이러스('2')
2. 빈칸 중에 3곳에 벽을 설치해야하고, 바이러스 역시 빈칸을 통해 퍼져나간다
3. 바이러스는 상하좌우로만 이동 가능하다
4. 바이러스가 최소로 퍼질 수 있도록 벽을 설치해야한다
5. 최대 영역의 개수(퍼지고 나서 빈칸의 개수)를 구해라

* 알고리즘

- 빈칸 중에서 벽 3개를 설치할 수 있는 모든 경우의 수를 고려: 브루트포스

- 바이러스가 빈칸('0')과 인접한 곳으로 퍼져나감: BFS

 

* 로직(Logic)

- 좌표를 관리하는 클래스를 활용해 빈칸('0')인 좌표들을 리스트에 넣어줌

- 나열된 리스트를 가지고 3개를 설치할 수 있는 모든 경우의 수를 진행

- 3개씩 설치될때마다 해당 3개의 좌표를 마킹하고 바이러스를 퍼뜨림

- 퍼뜨리고난 뒤 (전체 빈칸의 수 - 사다리3개 - 퍼진 바이러스 수) = 영역의 수를 통해 안전구역 개수를 리턴

- 최대 안전영역 개수 출력

 

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

class Position_14502{
    public int y,x;

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

public class Problem_14502 {

    static int n, m;
    static int[][] map;
    static boolean[][] checked; //bfs를 위한 마킹

    static ArrayList<Position_14502> lists; //빈칸('0')의 좌표를 담은 리스트
    static boolean[] mark;  //경우의 수를 구한 사다리 3개의 설치여부 마킹

    static Queue<Position_14502> queue_virus = new LinkedList<>();
    static Queue<Position_14502> queue_tmp;

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

    static int totalCnt = 0;    //빈칸의 전체 갯수
    static int max = 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];

        //0인 부분을 리스트에 담기
        lists = new ArrayList<>();
        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());
                if(map[i][j] == 0) {
                    lists.add(new Position_14502(i, j));
                    totalCnt++;
                }
                else if(map[i][j] == 2){
                    queue_virus.offer(new Position_14502(i, j));
                }
            }
        }

        //logic
        //리스트에 담긴 위치에서 사다리 3개를 설치할 수 있는 모든 경우의 수 구하기
        //3개를 설치하면 -> 바이러스를 퍼뜨리고 -> (전체 빈칸의 수 - 사다리3개 - 퍼진 바이러스 수) = 영역의 수 -> 최댓값 비교
        mark = new boolean[lists.size()];
        ArrayList<Integer> arrayList = new ArrayList<>();   //벽을 설치하는 좌표 경로
        for(int i=0; i<lists.size(); ++i){
            int installCnt = 1;
            doProcess(i, installCnt, arrayList);
        }

        System.out.println(max);
    }

    private static void doProcess(int index, int count, ArrayList<Integer> indexLists) {
        indexLists.add(index);
        mark[index] = true;

        if(count == 3){
            //바이러스를 퍼뜨려 안전영역 리턴
            int safeZone = spreadVirus(indexLists);
            max = Math.max(max, safeZone);

            //마지막에 추가된 경로를 제거해줘야 누적되지 않음
            indexLists.remove(indexLists.size()-1);
            mark[index] = false;

            return;
        }

        for(int i=0; i<lists.size(); ++i){
            if(!mark[i] && index != i){
                doProcess(i, count+1, indexLists);
            }
        }

        indexLists.remove(indexLists.size()-1);
        mark[index] = false;
    }

    private static int spreadVirus(ArrayList<Integer> indexLists) {
        checked = new boolean[n][m];
        for(int i=0; i<indexLists.size(); ++i){
            checked[lists.get(indexLists.get(i)).y][lists.get(indexLists.get(i)).x] = true;
        }

        int virusNum = 0;
        queue_tmp = new LinkedList<>();
        boolean check = false;

        while (!queue_virus.isEmpty()){
            int size = queue_virus.size();
            if(check) virusNum += size;
            for(int i=0; i<size; ++i){
                Position_14502 q = queue_virus.poll();
                if(!check) queue_tmp.offer(q);

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

                    if(isRanged(moveY, moveX) && !checked[moveY][moveX] && map[moveY][moveX] == 0){
                        queue_virus.offer(new Position_14502(moveY, moveX));
                        checked[moveY][moveX] = true;
                    }
                }
            }
            check = true;
        }

		//바이러스 위치들 다시 담기
        while (!queue_tmp.isEmpty()){
            queue_virus.offer(queue_tmp.poll());
        }

        //(전체 빈칸의 수 - 사다리3개 - 퍼진 바이러스 수) = 영역의 수
        int safeZone = totalCnt - indexLists.size() - virusNum;
        return safeZone;
    }

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

 

모든 경우의 수를 구할 때 내가 사용한 방식은 예를 들어, (0,1), (2,3), (3,5)과 (2,3), (3,5), (0,1)의 경우를 모두 고려한다. 즉, 중복되는 경우까지 경우의 수로 고려하는건데 이러한 방식보다는 [퇴사]문제에서 사용한 재귀 방식으로 중복되는 요소는 더이상 탐색하지 않는다면 시간이나 메모리적으로 소요가 덜 들거 같다는 생각을 했다.