[SWEA-2383] 점심 식사시간

이 문제는 SWEA에 있는 점심 식사시간이라는 문제이다. 

문제를 가지고 오긴 했지만, 문제가 너무 길어서 예시를 하나 밖에 못 가지고 왔다.

혹시 전체 문제가 궁금한 사람들은 이미지를 클릭하면 문제 페이지로 넘어가도록 링크를 걸어두었으니 들어가보세용!

 

 

이 문제도 어떻게 풀까 고민을 많이 했던 문제이다.

처음에는 가까운 계단에 PriorityQueue를 이용해서 넣어볼까 했는데 만약 한 곳으로 사람이 몰려서 대기시간이 길어지거나 계단에는 3명까지만 올라갈 수 있는데, 현재 계단에 몇 명 있는지 카운트하기가 어려울 것 같았다.

그래서 이런 저런 시도를 다 해보다가 결국 모든 집합을 다 구해보는 것을 택했다.

 

1. powerset을 이용해 각 사람이 0번 계단으로 갈 지, 1번 계단으로 갈 지 정해주기(powerset)

2. 계단에 있는 애들을 먼저 처리해주고 아직 계단에 도착하지 못한 사람들과 계단에서 기다리고 있는 사람들 처리

 

크게 보면 이게 다긴 하다.

지난번거에 비해 코드가 복잡하니까 powerset부터 하나씩 보자.

1) 어차피 계단은 2개니까 selected의 값이 true면 0번 계단, false면 1번 계단으로 가게 설정해주고

2) Point라는 자료형을 이용해 LinkedList를 만들어서 각 점에서 계단까지의 거리, 몇 번째 계단인지, 선택한 계단의 길        이를 넣어준다. 계단에 도착하더라도 1턴 더 기다려야 하니까 처음부터 계단까지의 거리를 1 늘려서 저장해주었다.

3) 다 넣었으면 calculate로 이동시킨다. 

 

static void powerset(int cnt) {
		if(cnt == idx){
			ppl = new LinkedList<>();
			int a = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == 1) {
						if(selected[a++]) { //true면 0번 계단
							int dir = Math.abs(stair[0].r-i)+ Math.abs(stair[0].c-j);
							//계단 올라가도 한칸 더 기다려야 하니까
							ppl.add(new Point((dir+1),0,stair[0].len));
						}
						else { //false면 1번 계단
							int dir = Math.abs(stair[1].r-i)+ Math.abs(stair[1].c-j);
							ppl.add(new Point((dir+1),1,stair[1].len));
						}
					}
				}
			}
			
			calculate(idx);
			return;
		}
		
		selected[cnt] = true;
		powerset(cnt+1);
		selected[cnt] = false;
		powerset(cnt+1);
	}

 

 

그 후 calculate!

이 코드의 핵심 로직 부분이다. 

여기서 계산을 잘 못 해줘서 계속 45/50 이였는데 결국 고쳤다ㅎㅎ

 

1) 아까 powerset에서 만든 LinkedList가 빌 때 까지 while문을 돌린다.

2) 계단에 올라와 있는 사람들을 먼저 처리한다.

  2-1) 계단에 도착했다면, 일단 턴을 넘긴다. (뒤에서 다시 처리해 줄 것)

  2-2) 계단을 내려가고 있는 중이라면 계단을 계속 내려간다.

  2-3) 계단을 다 내려갔다면 계단에서 빼 준다. 

3) 계단에 도착하지 못한 사람이 있다면 계단을 향해 가준다

4) 대기중인 사람이 있는데, 계단에 자리가 있다면 계단으로 들어간다. 

 

2번을 먼저 처리해주는 이유는

1번 사람이 대기중일 때, 같은 턴에 2번 사람이 나갔다면 대기중이던 1번 사람은 계단으로 들어가야 한다. 

하지만 for문의 순서 상 1번이 먼저 처리되기 때문에 자리가 났다고 하더라도 1번은 새 자리에 들어갈 수 없다.

그래서 두 개를 나눠주었다.

 

static void calculate(int idx) {
		int cnt = 0;
		while(!ppl.isEmpty()) {
			cnt++;
			int a = 0;
			int b = 0; 
			//계단에 있는 애들 먼저 처리
			for(int i=0; i<idx; i++) {
				Point p = ppl.get(i);
//				System.out.print((p.dir+p.cnt)+" ");
				if(p.dir == 0){ //계단에 도착한 애들 중에1
					if(p.cnt == stair[p.n].len) //계단 들어가고 싶으면 일단 대기
						continue;
					if((p.cnt > 0) && (p.cnt < stair[p.n].len)) {//p가 계단 내려가는 중이면 계속 내려가기
						p.cnt -= 1;
					}
					if(p.cnt == 0) {//이번턴에 계단 끝 도착했으면 나가기
						if(p.n == 0)
							a++;
						else
							b++;
						ppl.remove(p);
						i--;
						idx--;
					}
				}
			}
			
//			System.out.println();
			for(int i=0; i<idx; i++) {
				Point p = ppl.get(i);
				if(p.dir > 0) {//아직 계단에 도착 못했으면 이동
					p.dir -= 1;
				}
				//아까 계단 도착했던 애들 중에 들어갈 수 있으면 들어가기. 
				else if((p.dir == 0) && (p.cnt == stair[p.n].len) && (stair[p.n].cnt < 3)){
					stair[p.n].cnt += 1;
					p.cnt -= 1;
				}
			}
			stair[0].cnt -= a;
			stair[1].cnt -= b;
		}
		
		if(cnt < ans)
			ans = cnt;
	}

 

 

 

이제 전체 코드!

import java.util.LinkedList;
import java.util.Scanner;

public class 점심식사시간 {
	static int N,idx,ans;
	static Stair[] stair; //계단
	static int[][] map;

	static boolean[] selected;
	static LinkedList<Point> ppl;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int tc=1; tc<=T; tc++) {
			
			N = sc.nextInt();
			map = new int[N][N];
			stair = new Stair[2]; //계단
			
			idx = 0;
			ans = 100000;
			int s = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					map[i][j] = sc.nextInt();
					if(map[i][j] > 1) {
						stair[s++] = new Stair(i,j,map[i][j],0);
					}
					else if(map[i][j] == 1){
						idx++;
					}
				}
			}
			
			selected = new boolean[idx];
			powerset(0);
			
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	
	static void powerset(int cnt) {
		if(cnt == idx){
			ppl = new LinkedList<>();
			int a = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == 1) {
						if(selected[a++]) { //true면 0번 계단
							int dir = Math.abs(stair[0].r-i)+ Math.abs(stair[0].c-j);
							//계단 올라가도 한칸 더 기다려야 하니까
							ppl.add(new Point((dir+1),0,stair[0].len));
						}
						else { //false면 1번 계단
							int dir = Math.abs(stair[1].r-i)+ Math.abs(stair[1].c-j);
							ppl.add(new Point((dir+1),1,stair[1].len));
						}
					}
				}
			}
			
			calculate(idx);
			return;
		}
		
		selected[cnt] = true;
		powerset(cnt+1);
		selected[cnt] = false;
		powerset(cnt+1);
	}
	
	static void calculate(int idx) {
		int cnt = 0;
		while(!ppl.isEmpty()) {
			cnt++;
			int a = 0;
			int b = 0; 
			//계단에 있는 애들 먼저 처리
			for(int i=0; i<idx; i++) {
				Point p = ppl.get(i);
//				System.out.print((p.dir+p.cnt)+" ");
				if(p.dir == 0){ //계단에 도착한 애들 중에1
					if(p.cnt == stair[p.n].len) //계단 들어가고 싶으면 일단 대기
						continue;
					if((p.cnt > 0) && (p.cnt < stair[p.n].len)) {//p가 계단 내려가는 중이면 계속 내려가기
						p.cnt -= 1;
					}
					if(p.cnt == 0) {//이번턴에 계단 끝 도착했으면 나가기
						if(p.n == 0)
							a++;
						else
							b++;
						ppl.remove(p);
						i--;
						idx--;
					}
				}
			}
			
//			System.out.println();
			for(int i=0; i<idx; i++) {
				Point p = ppl.get(i);
				if(p.dir > 0) {//아직 계단에 도착 못했으면 이동
					p.dir -= 1;
				}
				//아까 계단 도착했던 애들 중에 들어갈 수 있으면 들어가기. 
				else if((p.dir == 0) && (p.cnt == stair[p.n].len) && (stair[p.n].cnt < 3)){
					stair[p.n].cnt += 1;
					p.cnt -= 1;
				}
			}
			stair[0].cnt -= a;
			stair[1].cnt -= b;
		}
		
		if(cnt < ans)
			ans = cnt;
	}

	static class Stair{
		int r,c,len,cnt; //계단 위치, 계단 길이, 올라가 있는 사람
		Stair(int r, int c, int len, int cnt){
			this.r = r;
			this.c = c;
			this.len = len;
			this.cnt = cnt;
		}
	}
	
	
	static class Point{
		int dir,n,cnt; //계단까지의 거리, 몇 번째 계단인지, 계단 길이
		Point(int dir,int n, int cnt){
			this.dir = dir;
			this.n = n;
			this.cnt= cnt;
		}	
	}
}

 

 

주말에 시험이 있어서 며칠 포스팅을 못했다.

하루에 하나라도 올리려고 노력중이였는데... 다시 화이팅ㅎㅅㅎ