(Java) 2105. [모의 SW 역량테스트] 디저트 카페

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

마찬가지로 완전 탐색 문제.
– 대각선으로 간다고 해서 복잡하게 생각하지 말고, 경우를 나누면 됨
(예를 들어 4X4에서 대각선으로 갈 수 있는 경우는 3X3 사각형에서 위쪽 가운데에서 마름모 모양으로 내려오는 경우 1개, 4X4 사각형에서 오른쪽 대각 방향 사각형, 왼쪽 대각 방향 사각형 2개 해서 총 3가지 종류이다.)
– 이를 일반화하면 다음과 같다.
3X3 사각형에서 (1,0)에서 좌-하-우-상으로 순회하는 사각형 1개 (총 1개)
4X4 사각형에서 (1,0)에서 좌-하-우-상으로 순회하는 사각형 1개, (2,0)에서 좌-하-우-상으로 순회하는 사각형 1개 (총 2개)
5X5 사각형에서 (1,0)에서 좌-하-우-상으로 순회하는 사각형 1개, (2,0)에서 좌-하-우-상으로 순회하는 사각형 1개, (3,0)에서 좌-하-우-상으로 순회하는 사각형 1개 (총 3개)
….
– 이를 활용해서 실제 지도에서 값을 구할 때는 (N이 5라고 가정)
5X5 맵에서 3X3 사각형을 총 9개 (솔루션 1개*가능한 위치 9개), 4X4 사각형을 총 8개 (솔루션 2개*가능한 위치 4개), 5X5 사각형을 총 3개 (솔루션 3개*가능한 위치 1개) 해서 총 20번 탐색하면 된다.
이 중 사각형이 끝까지 이어진 경우만 모아서 종류의 최대값을 구하면 문제에서 원하는 답이 나옴.
– 최적화를 위해, 테스트 케이스 이어질 때 이미 구한 사각형 종류는 중복해서 구하지 않도록 함 (너무 꼼수 같아서 뺐음)

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

public class Solution {
	// 크기 별 가능한 순회 모양 세트
	public static TreeMap<Integer, List<List<String>>> solutionCases = new TreeMap<Integer, List<List<String>>>();
	
	public static void main(String[] args) throws IOException {
		//System.setIn(new FileInputStream("./src/sample_input.txt"));

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int i = 0; i < numCases; i++) {
				writer.write("#" + String.valueOf(i + 1) + " ");
				
				int numN = Integer.parseInt(reader.readLine());
				int maxValue = -1;	// 갱신된 적이 없는 경우 (=가능한 경우 없음) -1 출력
				
				// Map 생성
				int[][] map = new int[numN][numN];
				for (int j = 0; j < numN; j++) {
					String[] tmp = reader.readLine().split(" ");
					
					for (int k = 0; k < numN; k++) {
						map[k][j] = Integer.parseInt(tmp[k]);
					}
				}
				
				solutionCases.clear();

				// 3*3부터 N*N까지 순회 가능한 케이스 모두 작성
				for (int j = 3; j <= numN; j++) {
					solutionCases.put(j, new ArrayList<List<String>>());
					
					// 상단 edge에서 왼쪽 edge -> 하단 edge -> 오른쪽 edge -> 상단 edge로 돌아온다고 가정했을 때,
					// 출발 가능한 곳은 (1,0)부터 (j-2,0)까지임 (즉, 두번째부터 끝에서 두번째까지)
					List<String> startPoints = new LinkedList<String>();
					for (int k = 1; k <= j - 2; k++)
						startPoints.add(k + "/0");
					
					// 시작점 별로 사각형을 그림
					for(String startPoint: startPoints) {
						String[] tmp = startPoint.split("/");
						int x = Integer.parseInt(tmp[0]);
						int y = Integer.parseInt(tmp[1]);
						
						List<String> pathInfo = new ArrayList<String>();
						
						// 1단계: 왼쪽 edge로 (x--, y++)
						while (x > 0) {
							pathInfo.add("-1/1");
							
							x--;
							y++;
						}
						
						// 2단계: 하단 edge로 (x++, y++)
						while (y < j - 1) {
							pathInfo.add("1/1");
							
							x++;
							y++;
						}
						
						// 3단계: 오른쪽 edge로 (x++, y--)
						while (x < j - 1) { pathInfo.add("1/-1"); x++; y--; } // 4단계: 상단 edge로 (x--, y--) while (y > 0) {
							pathInfo.add("-1/-1");
							
							x--;
							y--;
						}
						
						solutionCases.get(j).add(pathInfo);
					}
				}
			
				// 맵에 따라 실제로 탐방 
				// (numN=4이면 3*3은 시작점이 (1,0), (1,1), (2,0), (2,1)이고
				// 4*4는 처음 사각형은 시작점은 (1,0), 두번째 사각형은 시작점이 (2,0)) 
				for (int j = 3; j <= numN; j++) {
					List<List<String>> solutionCase = solutionCases.get(j);
					
					int tmp_ = solutionCase.size();
					
					// J*J의 각 솔루션(=각 사각형) 별로 실제 맵에 매핑될 수 있는 위치들을 구함  
					for (int k = 0; k < tmp_; k++) {
						int startX = k + 1;	// 시작점 (X)
						int startY = 0;		// 시작점 (Y)
						
						// 시작점 기준 실제 맵에서 가능한 경우의 수 모두 탐색
						List<String> offsetList = new ArrayList<String>();
						for (int l = 0; l <= numN - j; l++) {
							for (int m = 0; m <= numN - j; m++) {
								offsetList.add(l + "/" + m);
							}
						}
						
						// 모든 가능한 경우 별로 디저트 수 카운트
						for (String offset: offsetList) {
							String[] tmp__ = offset.split("/");
							int offsetX = Integer.parseInt(tmp__[0]);
							int offsetY = Integer.parseInt(tmp__[1]);

							// 디저트 목록을 넣을 리스트
							List<Integer> dessertList = new ArrayList<Integer>();

							// 사각형의 점 갯수
							int tmp___ = solutionCase.get(k).size();
							
							// 실제 맵 내에서의 시작점 (X, Y)
							int X = startX + offsetX;
							int Y = startY + offsetY;
							
							// solutionCase를 순회하면서, dessert 값 더함
							for (int l = 0; l < tmp___; l++) { int dessertValue = map[X][Y]; // 아직 없는 디저트라면 OK if (dessertList.contains(dessertValue) == false) { dessertList.add(dessertValue); // 다음 이동 방향대로 X, Y를 이동 String[] nextDirection = solutionCase.get(k).get(l).split("/"); X += Integer.parseInt(nextDirection[0]); Y += Integer.parseInt(nextDirection[1]); } else // 이미 있는 디저트면 루프를 더 돌지 않음 break; } // 순회를 다 못한 경우는 제외 if (dessertList.size() != solutionCase.get(k).size()) continue; // 순회를 다한 경우, 최대값 갱신 if (dessertList.size() > maxValue)
								maxValue = dessertList.size();
						}
					}
				}
				
				writer.write(maxValue + System.lineSeparator());
				writer.flush();
			}			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.