[SWEA] 4408 자기방으로 돌아가기 JAVA

문제링크 

SW Expert Academy

 

1. 문제 유형 및 이해

Greedy

 '최단 시간에' 모든 학생이 자신의 방으로 돌아가야 한다.

 1 단위 시간에 갈 수 있는 최대한 많은 학생이 방으로 돌아갈 수 있게 하여 최단 시간에 끝내야 된다고 생각했고,

그리디 알고리즘이라고 생각했다.

 

2. 문제 접근 방법

단위 시간에 최대한 많은 학생들이 방으로 들어가도록 해야한다. 즉, 동선이 절대로 겹쳐서는 안된다고 생각했다.

 2-1. 동선이 절대로 겹쳐서는 안돼! 근데 방의 위치가?

   Room 1과 Room2 Room3과 Room4는 결국 같은 위치라고 볼 수 있다. 

   위치를 압축하기 위해 각각의 room Number에 대해서 /2를 통해 압축했다.
   주어지는 동선 [a,b]와 [c,d]는 절대로 겹쳐서는 안된다. 

   동선의 위치를 압축하고 각 동선을 구분하기 위해서 [start, end] 일 때, 
   항상 start < end로 만들어주고자 했다.
   들어오는 값 (a,b)라면 [ Math.min(a,b), Math.max(a,b)] 로 구성하면 쉽게 구성할 수 있다.

2-2. 동선을 정렬하고 차곡차곡 복도를 최대한 많이 채워보자.

  이 부분에서 가장 큰 오류를 범했었다.

 이미 풀어본 문제인 [백준 - 회의실 배정] 처럼 생각하고 접근했다.
 둘의 차이는 다음과 같다.

• 회의실 배정문제
  X 시간 안에 최대한 많은 수를 집어넣기 위해 종료시간이 가장 짧은 것을 택해 
  남은 시간을 길게 하여 최대한 많은 회의를 넣어보자.
  즉, 어떤 선분 안에 최대한 많은 경우를 넣는다.
• 자기방으로 돌아가기
  규칙을 만족하여 X 복도를 꽉꽉 채우기.
  즉, 어떤 선분을 가장 꽉 채울 수 있는 방법.

만약 길이가 11인 선분이 있고 이를 채우기 위한 작은 선분들이 있다고 가정해보자.
1, 2, 3, 4, 5
회의실 배정 문제라면 1,2,3,4 또는 1,2,3,5 로 4개가 최대의 개수가 되는 경우를 찾는 거고
자기 방으로 돌아가기 문제라면 2,4,5 1,2,3,5와 같이 최대한 11을 채우기 위한 문제이다.

비슷해보이지만 전혀 다른 문제이다. 이 문제에서 또한 다음과 같은 반례가 존재한다
(110 120) (50 60) (130 90) (100 40)

 

마지막 방을 기준으로 정렬을 하고 어떠한 동선 [a,b]를 택한 후 다음 동선 [c,d]가 [a,b]와 겹치지 않는다면, 택하는 방식으로 최대한 많은 동선을 택해 보자.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for(int tt=1;tt<=T;tt++){
            sb.append('#').append(tt).append(' ');
            int N = Integer.parseInt(br.readLine());
            ArrayList<Point> info = new ArrayList<>();
            for(int i =0;i<N;i++){
                st = new StringTokenizer(br.readLine());
                int u = Integer.parseInt(st.nextToken())-1;
                int v = Integer.parseInt(st.nextToken())-1;
                //방 압축
                u = u/2;
                v = v/2;
                info.add(new Point(Math.min(u,v), Math.max(u,v)));
            }
            info.sort(Point::compareTo);
            Queue<Point> queue = new LinkedList<Point>(info);
            int cnt =0 ;
            while (!queue.isEmpty()) {
            Point prev = new Point(-1, -1);
                int size = queue.size();
                for(int i =0;i<size;i++){
                    Point cur = queue.poll();
                    if (prev.to < cur.from) {
                        prev = cur;
                    }else{
                        queue.add(cur);
                    }
                }
                cnt++;
            }
            sb.append(cnt).append('\n');
        }
        System.out.println(sb);
    }
    static class Point implements Comparable<Point>{
        int from;
        int to;

        public Point(int from, int to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public int compareTo(Point o) {
            return this.from - o.from;
        }
    }
}

3. 다른 방법

동선을 모두 그렸다고 생각해보자. 결국 최대한 많이 겹친 부분을 어떻게든 해결해야하고, 이 부분은 끝까지 남아서 이 부분만 해결하면 된다. 결국 겹치는 부분을 counting하면서 제일 많이 겹치는 count가 답이 된다.

복도 한 곳에 지금 만약 3명이 겹친다면 어떻게 하더라도 3번 기다려야한다.
그렇다면 최대한 남에게 방해하지 않는 선에서 되도록 해야함.
왜냐하면 길수록 겹치는 구간이 크다면
겹치는 애들이 최대한 많은 애들이 가장 늦게 들어가야 더 많은 친구들이 움직일 수 있기 때문.