[ SWEA ] 2105. [모의 SW 역량테스트] 디저트 카페 - JAVA

swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

친구들과 디저트 카페 투어를 할 계획이다.

[Fig. 1]과 같이 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.

원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고

카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.

디저트 카페 투어는 어느 한 카페에서 출발하여

[Fig. 2]와 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.
 
 

디저트 카페 투어를 하는 도중 해당 지역을 벗어나면 안 된다.

또한, 친구들은 같은 종류의 디저트를 다시 먹는 것을 싫어한다.

즉, [Fig. 3]과 같이 카페 투어 중에 같은 숫자의 디저트를 팔고 있는 카페가 있으면 안 된다.
 
 

[Fig. 4]와 같이 하나의 카페에서 디저트를 먹는 것도 안 된다.

 

[Fig. 5]와 같이 왔던 길을 다시 돌아가는 것도 안 된다.
 

 

친구들과 디저트를 되도록 많이 먹으려고 한다.

디저트 가게가 모여있는 지역의 한 변의 길이 N과 디저트 카페의 디저트 종류가 입력으로 주어질 때,

임의의 한 카페에서 출발하여 대각선 방향으로 움직이고

서로 다른 디저트를 먹으면서 사각형 모양을 그리며 다시 출발점으로 돌아오는 경우,

디저트를 가장 많이 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하는 프로그램을 작성하라.

만약, 디저트를 먹을 수 없는 경우 -1을 출력한다.


[예시]

한 변의 길이 N이 4인 지역에 디저트 카페가 [Fig. 6]과 같이 있다고 생각하자.
 

디저트 카페 투어가 가능한 경우는 [Fig. 7]과 같이 5가지로 나눌 수 있다.

(출발한 곳과 도는 방향은 다를 수 있지만, 디저트 카페 투어의 경로가 그리는 사각형 모양은 5가지 중 하나이다.)

 

[Fig. 7]

 
이 중에 디저트를 가장 많이 먹을 수 있는 경우는 ⑤인 경우로 디저트의 종류는 6개이다.

따라서, 정답은 6이 된다.


[제약사항]

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초

2. 디저트 카페가 모여있는 지역의 한 변의 길이 N은 4 이상 20 이하의 정수이다. (4 ≤ N ≤ 20)

3. 디저트 종류를 나타나는 수는 1 이상 100 이하의 정수이다.


[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.


[출력]

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

 

[ 풀이 ] 

이 문제는 직전에 풀엇던, 백준의 17779번 게리맨더링 2랑 매우 유사한 알고리즘으로 풀 수 있는데, 

그러면 쉽게 풀린다. 

[ 풀이 코드 ] 

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

public class 디저트카페 {	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb =new StringBuilder();
		for(int t = 0; t<T; t++) {
			int N = Integer.parseInt(br.readLine().trim());
			int [][] arr =new int[N][N];
			for(int i =0; i< N ;i++) {
				StringTokenizer st =new StringTokenizer(br.readLine());
				for(int j = 0; j< N ; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}// 입력 끝 
			int ans = -1;
			// 필요한거 시작점(x,y),왼쪽, 오른쪽 길이( R, L), 중복 확인용 Set
			for(int X = 0 ; X< N; X++) {
				for(int Y = 0;Y<N; Y++ ) {
					for(int L = 1; Y-L>=0 ; L++ ) {
						for(int R = 1;Y+R<N &&X+R+L<N ; R++ ) {
							HashSet<Integer> hs = new HashSet<Integer>();
							//hs.add(arr[X][Y]);
							boolean dup = true;
							for(int i =1; i<=R && dup; i++) {
								if(hs.contains(arr[X+i][Y+i])) {
									dup =false;
									break;
								}
								hs.add(arr[X+i][Y+i]);
							}
							for(int i=1; i<=L && dup; i++) {
								if(hs.contains(arr[X+R+i][Y+R-i])) {
									dup = false;
									break;
								}
								hs.add(arr[X+R+i][Y+R-i]);
							}
							for(int i =1; i<=R && dup ; i++) {
								if(hs.contains(arr[X+R+L-i][Y+R-L-i])) {
									dup = false;
									break;
								}
								hs.add(arr[X+R+L-i][Y+R-L-i]);
							}
							for(int i =1; i<=L && dup; i++) {
								if(hs.contains(arr[X+L-i][Y-L+i])) {
									dup = false;
									break;
								}
								hs.add(arr[X+L-i][Y-L+i]);
							}
							if(dup) {
								ans = ans<hs.size()?hs.size():ans;
							}
						}
					}
				}
			}
			sb.append('#').append(t+1).append(' ').append(ans).append('\n');
		}
		System.out.println(sb);
	}
}

그래서 바로 풀 수 있었다. 마찬가지로 단순한 시뮬레이션 문젠데, 

반복문만 4중으로 돌면 풀 수 있다. 

 

여기까지는 입력을 받ㄷ아서 들어온 값들을 모두 저장해 준다. 

그리고 ans 도 -1로 초기화 해서 나중의 답 입력 때 이용한다. 

그리고 이제 반복문을 돌면서 대각선 네모를 그려야 하는데, 이전의 게리맨더링2의 팁으로 

이 네가지가 있다면 쉽게 구할 수 있다는 것을 알 수 있다. 

따라서 먼저 이 네가지를 반복문을 사용해서 완탐 할 수 있도록 적어준다. 

 시작점을 (X,Y)로 정하고, 그리고,왼쪽으로 그릴 길이, 오른쪽으로 그릴 길이 해서 (L,R)을 정한다 이후 디저트가 중복되면 안되니, 중복 확인용 Set까지 선언한다. 

그리고 차례대로 4번 오른쪽 아래, , 그 점부터 시작한 왼쪽 아래, 그리고 이후 점부터 시작한, 왼쪽 위, 오른쪽 위 

순서로 다시 반복문을 돌면서 진행한다. 

사실 처음에는 goto 문을 쓰면 좋겠지만, 사실 goto문은 별로 좋지 않다고 해서 그냥 dup이라는 버튼 하나를 넣어놓았다.

시작 점과 값들만 계산하면 차례대로 시뮬레이션이 가능하다. 

그리고 중복 검사를 하고 중복이 없고, ans 값이 더 크다면 값을 넣어주고,

sb라는 StringBuilder에 값을 담으면서 

 

마지막으로 T값을 모두 돌고, 이후에 한번에 sb를 출력해주면 되는 시뮬레이션 문제이다.