글 읽기 - 반례좀 알려주실분 있나요.. 정말 풀고싶습니다..

redbin0471 3년 전 0

몇시간째 붙잡고 잇는지 모르겠습니다. 반례가 생각나지 않습니다.

고수님들 부탁드립니다.

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

public class 정육면체전개도 {
	static int map[][] = new int[6][6];
	static boolean col[] = new boolean[6];
	static boolean row[] = new boolean[6];
	static int y;
	static int x;
	// 20 개 가능 케이스
	static String check[][] = { { "222", "1221" }, { "1221", "222" }, { "11211", "33" }, { "33", "11211" },
			{ "1221", "231" }, { "1221", "132" }, { "132", "1221" }, { "231", "1221" }, { "222", "1212" },
			{ "222", "2121" }, { "2121", "222" }, { "1212", "222" }, { "231", "1131" }, { "132", "1131" },
			{ "231", "1311" }, { "132", "1311" }, { "1131", "231" }, { "1131", "132" }, { "1311", "231" },
			{ "1311", "132" } };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		// 3 test case
		for (int t = 1; t <= 3; t++) {
			// map input
			int e = 0;
			for (int i = 0; i < 6; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 6; j++)
					e += map[i][j] = Integer.parseInt(st.nextToken());
			}
			if (e != 6) {
				System.out.println("no");
				continue;
			}

			// 정육면체 가능한지 테스트
			Arrays.fill(col, false);
			Arrays.fill(row, false);
			boolean ans = false;

			// 4가지 블록 테스트
			String r = new String();
			String c = new String();
			// c 채우기
			for (int i = 0; i < 6; i++) {
				int cnt = 0;
				for (int j = 0; j < 6; j++)
					cnt += map[i][j];
				c += cnt + "";
			}
			c= String.valueOf(Integer.parseInt(c));
			c = String.valueOf(new StringBuilder(c).reverse());
			c = String.valueOf(new StringBuffer(String.valueOf(Integer.parseInt(c))).reverse());
			// r 채우기
			for (int j = 0; j < 6; j++) {
				int cnt = 0;
				for (int i = 0; i < 6; i++)
					cnt += map[i][j];
				r += cnt + "";
			}
			r= String.valueOf(Integer.parseInt(r));
			r = String.valueOf(new StringBuilder(r).reverse());
			r = String.valueOf(new StringBuffer(String.valueOf(Integer.parseInt(r))).reverse());
			
			System.out.println(r);
			System.out.println(c);
			for (int s = 0; s < 20; s++) {
				if (check[s][0].equals(r) && check[s][1].equals(c)) {
					ans = true;
					break;
				}
			}

			if (!ans)
				for (int i = 0; i < 6; i++) {
					if (ans)
						break;
					for (int j = 0; j < 6; j++) {
						if (ans)
							break;
						if (map[i][j] == 1) {
							// 1인걸 발견하면 길이가 4인 녀석을 찾는다 이미 방문한 녀석은 찾지않는다.
							// 지금 지점을 포함해서 아래쪽으로 길이가 몇인지 계산한다.
							if (!col[j]) {
								col[j] = true;
								y = i;
								x = j;
								int len = 0;
								while (true) {
									if (y < 0 || y >= 6 || x < 0 || x >= 6)
										break;
									if (map[y][x] == 0)
										break;
									len++;
									y++;
								}

								// 아래방향 이므로 정육면체가 가능한지 테스트
								if (len == 4 && j != 0 && j != 5) {
									// x를 기준으로 왼쪽에 한개 오른쪽에 한개잇으면 정사각형
									int a = 0;
									int b = 0;
									for (int l = i; l < i + 4; l++) {
										if (map[l][j - 1] == 1) {
											a++;
										}
										if (map[l][j + 1] == 1) {
											b++;
										}
									}
									if (a == 1 && b == 1) {
										ans = true;
									}
								}

							}

							if (!row[i]) {
								row[i] = true;
								y = i;
								x = j;
								int len = 0;
								while (true) {
									if (y < 0 || y >= 6 || x < 0 || x >= 6)
										break;
									if (map[y][x] == 0)
										break;
									len++;
									x++;
								}

								// 아래방향 이므로 정육면체가 가능한지 테스트
								if (len == 4 && i != 0 && i != 5) {
									// y를 경계로 위아래로 한개씩 있으면 정육면체
									int a = 0;
									int b = 0;
									for (int l = j; l < j + 4; l++) {
										if (map[i + 1][l] == 1) {
											a++;
										}
										if (map[i - 1][l] == 1) {
											b++;
										}
									}
									if (a == 1 && b == 1) {
										ans = true;
									}
								}

							}

						}
					}
				}
			String answer = ans ? "yes" : "no";
			System.out.println(answer);
		}
	}

	public static int[][] rotate(int[][] map) {
		int copy[][] = new int[6][6];
		for (int i = 0; i < 6; i++) {
			for (int j = 0; j < 6; j++) {
				copy[i][j] = map[j][6 - i - 1];
			}
		}

		return copy;

	}
}

wjdchs0129 2년 전 1

고수는 아니지만, (사실 코드도 13~18번줄만 읽었어요) 제가 푼 방식을 설명드릴게요.

가능한 전개도를 인터넷에 찾아보시면 기본형 11개가 있습니다.(정육면체의 전개도는 몇개일까? (sigan.kr))

이 11개 각각을 뒤집(flip)을수도 있겠죠. 그럼 안뒤집은거(원형) 11개, 뒤집은거 11개해서 총 22개가 있습니다.

여기서 각각 회전(rotate)을 0도(기본형 원형), 90도, 180도, 270도 하면 각 모양별 4가지가 있습니다.

그럼 총 22 * 4 = 88 개가 되겠죠.

그럼 입력으로 주어진 도형이 이 88개의 도형 내에 들어있는지 확인 시켰더니 바로 맞았습니다.

* 주어진 도형의 테두리가 0으로'만' 둘러싸여 있다면 제거후 깔끔히 만들었고, 88개의 도형 중 위 링크의 첫번째 파란색 도형을 다음과 같이 표기했습니다.

Python : ['1000', '1111', '1000']

redbin0471 2년 전 0

1년전 문제에 댓글을 달아주셧네요 ㅎㅎ 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례좀 알려주실분 있나요.. 정말 풀고싶습니다..

redbin0471 3년 전 0

wjdchs0129 2년 전 1

redbin0471 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말