백준 알고리즘 - 2477 참외밭

www.acmicpc.net/problem/2477

2477번: 참외밭

  백준 알고리즘의 2477번 문제, 참외밭입니다.

난이도는 실버5정도 되는데 문제를 이해하는 것은 별로 어렵지 않지만 실제로 구현하는데 더 나은 방법이 없는지 생각하다가 오래 걸렸습니다.

 

  어떤 참외밭이 있는데, 1m^2마다 수확되는 참외의 양이 정해져 있어 밭의 크기만 알면 해당 밭에서 참외가 얼마나 수확 가능한지 알 수 있습니다. 그런데 특이하게 모든 밭은 'ㄱ'이나 'ㄴ' 등과 같이 어디 한군데가 찌르러진 육각형인데다 서로 마주보게되는 변들이 전부 평행하여 직사각형 3개로 쪼개면 바로 넓이를 구할 수 있게 됩니다.

 

  예를 들면

 

1 1 1
1 1 1
1 1 1 1 1
1 1 1 1 1

 

  이런 식의 모양인 것이지요. 그런데 이건 이해를 위한 모양이지 실제로는 이렇게 입력을 주지 않습니다.

임의의 한 꼭짓점에서 시작해서 동 : 1, 서 : 2, 남 : 3, 북 : 4의 방향으로 가지고 얼마나 이동했는지을 같이 적어줍니다.

 

  예를 들면

 

7
4 50
2 160
3 30
1 60
3 20
1 100

 

  이렇게 첫번째 줄에 1m^2당 참외의 갯수를 알려주고 그 뒤로 6개의 변에대한 정보를 알려주는 것이지요. 이게 문제입니다. 정확하게 어느 부분이 움푹 패여들어간 부분인지 직관적으로 알 수 없습니다. 게다가 예시의 모양을 나타내는 방법은 총 12가지입니다.

 

423131 - 231314 - 313142 - 131423 - 314231 - 142313
242413 - 424132 - 241324 - 413242 - 132424 - 324241

 

  방향만 적었을 때, 423131과 같은 방향으로 한바퀴 도는 것을 표현할 수 있는 것이 6가지, 반대 방향으로 한바퀴 도는 것을 표현할 수 있는 것이 6가지로 총 12가지입니다. 그런데 이 안에서 움푹 패여들어간 부분을 알아내야 합니다.

  만일 알아내기만 한다면, 전체 크기에서 패여들어간 부분의 넓이를 빼면 육각형의 넓이를 알 수 있게 됩니다.

 

1 1 1 1 1          1 1      1 1 1
1 1 1 1 1   	   1 1      1 1 1
1 1 1 1 1   -            =  1 1 1 1 1
1 1 1 1 1                   1 1 1 1 1

 

  그런데 자세히 보면 423131의 6개 중에 2개가 2번 반복되는 것을 알 수 있습니다. 게다가 그 중에 가운데 2개가 움푹 패여들어간 부분의 각 변의 크기를 알려준다는 것을 알 수 있습니다.

 

  그래서 저는 int형 2차원 배열은 input에 해당 정보들을 넣고 6개 중에 2번 등장한 숫자 2개를 hint라는 배열에 넣고, 3131나 1313과 같은 모양이 발견될 때까지 input의 맨 앞 index 값을 빼서 맨 뒤로 넣어버렸습니다.

 

  만약 423131이라면 423131 -> 231314 -> 313142 (3131 발견!) / 이런식으로 2번 등장한 숫자 2개가 연속되어 있는 부분을 찾는 것입니다. 그러면 그 중에 3'13'1의 가운데 '13'에 각각 패여진 부분의 변의 크기를 알 수 있고, 이러면 자연스레 4와 2가 각각 전체 사각형의 변의 크기를 알려줍니다. 그러면 패여진 육각형의 크기를 구할 수 있습니다.

 

  아래는 제가 푼 코드입니다.

 

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

public class Main_BJ_2477_참외밭 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] input = new int[6][2];
		int[] count = new int[6];
		
		for(int i = 0; i < 6; i++) {
			StringTokenizer tk = new StringTokenizer(br.readLine(), " ");
			input[i][0] = Integer.parseInt(tk.nextToken());
			input[i][1] = Integer.parseInt(tk.nextToken());
			count[input[i][0] - 1]++;
		}

		int[] hint = new int[2];
		int index = 0;
		for(int i = 0; i < 6; i++) {
			if(count[i] == 2) hint[index++] = i+1;
		}
		
		
		// 423131 - 231314 - 313142 - 131423 - 314231 - 142313
		// 242413 - 424132 - 241324 - 413242 - 132424 - 324241

		int area = 0;
		
		for(int i = 0; i < 6; i++) {
			if((input[0][0] == hint[0] && input[1][0] == hint[1] && input[2][0] == hint[0] && input[3][0] == hint[1]) || 
					(input[0][0] == hint[1] && input[1][0] == hint[0] && input[2][0] == hint[1] && input[3][0] == hint[0])) {
				area = (input[4][1] * input[5][1]) - (input[1][1] * input[2][1]);
				break;
			}
			
			int[] temp = input[0].clone();
			for(int j = 0; j < 5; j++) {
				input[j] = input[j+1].clone();
			}
			input[5] = temp.clone();
		}
		
		
		
		// 동 : 1, 서 : 2, 남 : 3, 북 : 4
		

		System.out.println(area * N);
	}

}