[PS/JAVA] 모의 SW 역량테스트 SWEA 5644 : 무선 충전

문제

---

범준이의 제주도 여행 계획 : SWEA 5644

 

조건확인

---

1. 지도의 가로, 세로 크기는 10이다.

2. 사용자는 총 2명이며, 사용자A는 지도의 (1, 1) 지점에서, 사용자B는 지도의 (10, 10) 지점에서 출발한다.

3. 총 이동 시간 M은 20이상 100이하의 정수이다. (20 ≤ M ≤ 100)

4. BC의 개수 A는 1이상 8이하의 정수이다. (1 ≤ A ≤ 8)

5. BC의 충전 범위 C는 1이상 4이하의 정수이다. (1 ≤ C ≤ 4)

6. BC의 성능 P는 10이상 500이하의 짝수이다. (10 ≤ P ≤ 500)

7. 사용자의 초기 위치(0초)부터 충전을 할 수 있다.

8. 같은 위치에 2개 이상의 BC가 설치된 경우는 없다. 그러나 사용자A, B가 동시에 같은 위치로 이동할 수는 있다. 사용자가 지도 밖으로 이동하는 경우는 없다.

 

숫자	이동방향
0	이동하지 않음
1	상 (UP)
2	우 (RIGHT)
3	하 (DOWN)
4	좌 (LEFT)

 

풀이

---

1. 지도에 따른 입력값을 받는다

2. 사용자 2명의 위치는 고정되어있다는 것을 명시한다.

3. 이동 시간이 100이하 이므로 시간 복잡도를 구할 때 참고해보자.

4. 배터리의 개수가 주어졌다. 마찬가지로 시간 복자도를 구할 때 참고하자.

5. 충전 범위에 따른 범위설정을 해야 하는데, 이때 bfs를 이용해서 범위 설정을 했다.

6. 결과를 출력하기 위한 파워값이다. 혹시 산술 오버플로가 날지 생각해보자.

7. 사용자 초기위치부터 배터리 충전한다는 것을 간과하지 말자.

8. 사실상 이 문제의 핵심이다. 두 사용자가 같은 배터리를 공유했을 때 어떻게 처리할지가 관건이다. 더불어서 같은 배터리를 공유하는 것 뿐만아니라 한 사람이 배터리를 독차지하고 있다면 다른 사람은 파워를 얻지 못한다는 점이 중요하다.

이럴 때는 잠시 키보드를 놓고 경우의 수를 나눠 보는편이다. 같은 배터리를 공유했을 때 경우의 수는 다음과 같다.

• 사용중인 배터리가 없을 경우 : 얻는 파워는 없다.

• 사용중인 배터리가 하나일 경우 : 그 배터리의 파워를 뽑아낸다.

• 사용중인 배터리가 둘 그 이상일 경우 :

• 혹시 A혼자 독점하고 있지는 않을까?

• 혹시 B혼자 독점하고 있지는 않을까?

위와 같이 몇개의 배터리를 사용하고 있는지에 대한 접근으로 경우의 수를 나열해 보았다. 이렇게 나열 했지만 구현할 때 한가지 더 생각해야하는 것이 있다.

바로 둘 이상의 배터리를 사용할 때, 하나의 배터리는 A와 B가 공유하지만 나머지 하나는 A 혼자 사용한다고 한다면 이 배터리는 B -> A 순으로 파워를 계산해주어야 한다.

이 예시는 문제에서 따로 언급하고 있는만큼 중요한 부분인데, 나는 이를 정렬로 해결해 보았다.

 

구현

---

package SWEA;

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

public class SWEA_5644 {

    private static int T;
    private static int M;
    private static int A;
    private static int[] dirA;
    private static int[] dirB;

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

    private static int [][][] battery;
    private static int[] ddx = {0,1,0,-1};
    private static int[] ddy = {1,0,-1,0};
    private static int[] storage;

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

        for(int t = 1; t <= T; ++t) {
            st = new StringTokenizer(br.readLine());

            M = Integer.parseInt(st.nextToken());    // 이동시간
            A = Integer.parseInt(st.nextToken());    // 베터리 개수

            dirA = new int[M];
            dirB = new int[M];
            storage = new int[A];
            battery = new int[A][10][10];

            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < M; ++i) dirA[i] = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < M; ++i) dirB[i] = Integer.parseInt(st.nextToken()); 


            for(int i = 0; i < A; ++i) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken()) - 1;
                int y = Integer.parseInt(st.nextToken()) - 1;
                int c = Integer.parseInt(st.nextToken());    // 충전 범위
                int p = Integer.parseInt(st.nextToken());    // 처리량

                storage[i] = p;
                battery[i][y][x] = p;
                charge(i,y,x,c,p);    
            }

            sb.append("#" + t + " ").append(Solve()).append("\n");
        }
        System.out.println(sb);
    }

    private static int Solve() {
        int ay = 0;
        int ax = 0;
        int by = 9;
        int bx = 9;
        int i = 0;
        int ret = 0;

        do {            
            ret += batteryCheck(ay,ax,by,bx);

            if(i < M) {
                ay += dy[dirA[i]];
                ax += dx[dirA[i]];
                by += dy[dirB[i]];
                bx += dx[dirB[i]];
            }

            ++i;

        }while(i <= M);


        return ret;
    }


    private static int batteryCheck(int ay, int ax, int by, int bx) {
        List<int[]> tempList = new ArrayList<>();    //  (0,1,2) : (both,A,B) , power

        for(int i = 0; i < A; ++i) {
            if(battery[i][ay][ax] > 0 && battery[i][by][bx] > 0) {
                tempList.add(new int [] { 0, storage[i] } );    // both
                continue;
            }
            if(battery[i][ay][ax] > 0) {
                tempList.add(new int [] { 1, storage[i]} );        // A
                continue;
            }
            if(battery[i][by][bx] > 0) {
                tempList.add(new int [] { 2, storage[i]} );        // B
                continue;
            }
        }

        int ret = 0;
        int sz = tempList.size();
        if(sz > 1) {

            Collections.sort(tempList, new Comparator<int[]>() {

                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[1] > o2[1]) {
                        return 1;
                    } 
                    else if(o1[1] == o2[1]) {
                        if(o1[0] < o2[0]) return -1;
                        return 1;
                    }
                    return -1;
                }
            });


            boolean flagA = false;
            boolean flagB = false;
            int cnt = 0;

            for(int i = sz-1; i >= 0; --i) {
                int[] temp = tempList.get(i);
                int data = temp[1];
                int what = temp[0];

                if(what == 0) {
                    ret += data;
                    cnt++;
                }
                else if (what == 1) {
                    if(flagA) continue;
                    ret += data;
                    flagA = true;
                    cnt++;
                }
                else if (what == 2) {
                    if(flagB) continue;
                    ret += data;
                    flagB = true;
                    cnt++;
                }

                if(cnt == 2) break;
            }

        } else if(sz == 1) {
            ret += tempList.get(0)[1];
        }

        return ret;
    }

    private static void charge(int idx, int r, int c, int range, int power) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {r, c});

        int cnt = 1;
        while(q.size() != 0) {
            int sz = q.size();
            for(int i = 0; i < sz; ++i) {
                int temp[] = q.poll();
                int y = temp[0];
                int x = temp[1];

                for(int k = 0; k < 4; ++k) {
                    int ny = y + ddy[k];
                    int nx = x + ddx[k];

                    if(ny < 0 || ny >= 10 || nx < 0 || nx >= 10 || battery[idx][ny][nx] != 0) continue;
                    battery[idx][ny][nx] = power;
                    q.offer(new int[] {ny,nx});
                }
            }
            ++cnt;
            if(cnt > range) return; 
        }
    }
}

112 번째 줄에서 정렬을 해주고 있다. 이 때, (both,A사람,B사람) 을 (0,1,2) 로 치환하여 사용하고있는데 같은 배터리 파워를 가졌다면, 0보다는 1과 2가 먼저 나오도록 정렬을 하였다.

이유는 풀이 목차에서 마지막에 언급했던 조건을 충족시키기 위해서이다.

그리고 128번 줄부터 155번 줄 까지는 각 상태를 확인해서 만약 A사람 혹은 B사람이 배터리를 독차지 했을 경우를 방지 하고있다.

 

회고

---

푸는데 시간이 오래걸렸던 부분을 생각해본다면, 아무래도 경우의 수를 나누는 곳이 오래걸렸다. 내 코딩 스타일은 어느 정도 윤곽을 잡아놓고 코딩을 해가면서 그때그때 세세하게 조건을 해결하는 스타일이다. 그러나 이 스타일의 단점은, 한번 생각했던 내용이 꼬인다면 코드가 더럽더라도 꼬인대로 해결해나가려는 것이다. 따라서 이를 방지하기 위해 좀 더 꼼꼼하게 설계를 할 필요가있다. 그리고 만약 도중에 내용이 산으로 간다면 과감하게 다시 생각해보는 것도 방법중 하나라고 생각한다.