[SWEA 1798] 범준이의 제주도 여행계획

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4x9oyaCR8DFAUx&categoryId=AV4x9oyaCR8DFAUx&categoryType=CODE

SW Expert Academy

 

1. 이해하기

장소를 방문해서 만족도를 최대로 높이는 경우를 구하는 문제이다.

하루에 최대 9시간까지 사용할 수 있고 9시간 안에 호텔에 도착을 해야한다. 마지막 날이라면 9시간 내에 공항에 도착을 해야 한다.

그때의 최대 만족도와 경로를 구하는 문제이다.

모든 장소를 방문해 보는 완전탐색으로 푸는 문제이다.

 

2. 구현하기

매번 방문을 하면서 필요한 정보는 현재 위치, 남은 시간, 현재 만족도, 몇일 남았는지, 방문여부, 경로가 있다.

이를 함수에 그대로 적용한다.

이때 방문여부는 비트 연산자로 할 수 있다. 하지만 최대 N이 35가 될 수 있으므로 Long을 사용한다.

solve(x,t,s,m,visited,p)

이 함수가 끝나는 base case는 m이 0일 때이다. 즉 마지막 날일 경우이다. 이때는 현재 답과 현재 만족도를 비교하여 최대값과 방문 경로를 갱신해준다.

if(m == 0) {
	if(ans < s) {
		ans = s;
		path = new ArrayList<>();
		for(int e: p)
			path.add(e+1);
	}
	return;
}

이외의 경우에는

1. 다른 곳으로 놀러가는 경우.

2. 호텔에 들어가는 경우.

3. 공항에 가는 경우.

로 나뉘게 된다.

 

1. 다른 곳으로 놀러가는 경우

다른 곳으로, 방문하지 않았고, 시간이 충분하며, 호텔과 공항이 아닌 경우로 놀러간다.

for(int i = 0; i < N; i++) {
	if(i==x || (visited & (1L<<i)) != 0 || t-adj[x][i]-pt[i][0] < 0 || hotel[i] || airport==i) continue;
	p.add(i);
	solve(i,t-adj[x][i]-pt[i][0],s+pt[i][1],m,(visited | (1L<<i)),p);
	p.remove(p.size()-1);
	cnt++;
}

2. 호텔에 들어가는 경우

호텔에 들어가는 경우는 마지막 날이 아니고, 다른 곳으로 놀러갈 수 없는 경우에 호텔에 들어간다.

if(m != 1 && cnt == 0) {
	for(int i = 0; i < N; i++) {
		if(hotel[i] && t-adj[x][i] >= 0) {
			p.add(i);
			solve(i,9*60,s,m-1,visited,p);
			p.remove(p.size()-1);
		}
	}
}

3. 공항으로 가는 경우

마지막 날이며 다른 곳으로 놀러갈 수 없는 경우에 공항으로 간다.

else if(m == 1 && cnt == 0) {
	if(t-adj[x][airport] >= 0) {
		p.add(airport);
		solve(airport,9*60,s,m-1,visited,p);
		p.remove(p.size()-1);
	}
}

 

3. 전체코드

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

public class S1798범준이의제주도여행계획 {
	static int T,N,M;
	static int[][] adj;
	static boolean[] hotel;
	static int[][] pt;
	static int airport;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		T = sc.nextInt();
		for(int tc = 1; tc <= T; tc++) {
			sb.append("#"+tc+" ");
			N = sc.nextInt();
			M = sc.nextInt();
			adj = new int[N][N];
			hotel = new boolean[N];
			pt = new int[N][2];
			for(int i = 0; i < N-1; i++) {
				for(int j = i+1; j < N; j++) {
					adj[i][j] = sc.nextInt();
					adj[j][i] = adj[i][j];
				}
			}
			for(int i = 0; i < N; i++) {
				String c = sc.next();
				if(c.charAt(0)=='A') airport = i;
				else if(c.charAt(0)=='P') {
					pt[i][0] = sc.nextInt();
					pt[i][1] = sc.nextInt();
				} else {
					hotel[i] = true;
				}
			}
			
			ans = 0;
			path = new ArrayList<>();
			solve(airport,9*60,0,M,0,new ArrayList<>());
			sb.append(ans+" ");
			for(int p: path) {
				sb.append(p+" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	
	static int ans = 0;
	static List<Integer> path;
	static void solve(int x, int t, int s, int m, long visited, List<Integer> p) {
		if(m == 0) {
			if(ans < s) {
				ans = s;
				path = new ArrayList<>();
				for(int e: p)
					path.add(e+1);
			}
			return;
		}
		
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			if(i==x || (visited & (1L<<i)) != 0 || t-adj[x][i]-pt[i][0] < 0 || hotel[i] || airport==i) continue;
			p.add(i);
			solve(i,t-adj[x][i]-pt[i][0],s+pt[i][1],m,(visited | (1L<<i)),p);
			p.remove(p.size()-1);
			cnt++;
		}
		
		if(m != 1 && cnt == 0) {
			for(int i = 0; i < N; i++) {
				if(hotel[i] && t-adj[x][i] >= 0) {
					p.add(i);
					solve(i,9*60,s,m-1,visited,p);
					p.remove(p.size()-1);
				}
			}
		} else if(m == 1 && cnt == 0) {
			if(t-adj[x][airport] >= 0) {
				p.add(airport);
				solve(airport,9*60,s,m-1,visited,p);
				p.remove(p.size()-1);
			}
		}
	}
	
}

 

완탐일거라 생각을 못하고 다른 방법으로 접근을 시도하여 시간을 많이 소비했다.

완탐이 아닐 거라 생각했다면 그 이유를 명확하게 만들고 그 다음에 다른 방법을 시도하는 것이 좋겠다.