'알고리즘/삼성 SW 역량 테스트'에 해당되는 글 2건

14500번 주사위 굴리기

https://www.acmicpc.net/problem/14500

문제 해석

테트리스 게임을 조금 활용한 문제같습니다. 문제는 간단합니다.

어떤 판에 숫자들이 적혀있는데 여기서 테트리스모양으로 숫자를 골라 가장 최대가 나오는 값을 구하는 문제입니다.

테트리스 모양은 여러분들이 잘 아시죠? 여기서 물론 테트리스의 블록들은 4방향 회전이 가능합니다.

예제를 직접 풀어보도록 하지요. 아래의 문제의 첫번째 예제가 주어졌습니다.

여기서 가장 큰 수를 고르면 파랑색의 숫자들이 되겠습니다. 이 외에 더 큰 값을 테트리스 모양대로 고를수가 없는 것을 알 수 있습니다.

제약 조건

세로와 가로의 길이(N,M)은 4이상 500이하로 주어집니다. 입력으로 주어지는 수는 1000을 넘지 않는다고 합니다.

풀이

이 문제를 이전에 JAVA로 풀어놓은게 있으므로 이번 포스팅은 JAVA 코드로 구현했습니다.

가로와 세로의 길이는 최대 500이며, 숫자들은 모두 500x500으로 250,000개가 되겠네요. 또 이 중 최대 4개의 숫자만 더하면 되니 문제의 답은 총 4000을 초과하지 않습니다.

이와 같이 문제의 값의 범위가 적을때는 brute-force(전수조사)로 그 문제의 해답을 찾을 수 있습니다. 모든 가능한 수를 구하는 것입니다.

문제를 풀기에 앞서 손으로 테트리스 모양을 만듭시다. 총 7개의 모양을 가지고 있고, 4방향으로 회전을 하기 때문에 대략 28개의 테트리스 모양을 배열로 만들겁니다.

1은 블록이 있는 공간을 말하고 0은 블록이 없는 공간을 의미합니다. 이해가 더 잘가기 위해 아래 세가지 테트리스 블록을 그림으로 첨부했습니다.

이제 이것을 배열로 만드는 것이죠. 이렇게 말이죠. 이 정도 약간의 노가다는 해도 괜찮아요. 시간이 그렇게 많지 않으니까요.

static int [][][]shapes={
		{{1,1,1,1}},{{1},{1},{1},{1}}, 
		{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
		{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
		{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
		{{1,1},{1,1}},
		{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
		{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
};

배열 첫번째 모양은 일자모양(l)이고, 두번째는 ㅗ모양입니다. 세번째 모양은 L자 모양이 되겠습니다. 이것을 사방으로 회전하다 보니까 2차원 배열이 한 줄에 최대 4개까지 나오며, 일자모양과 정사각형 모양 등 네 방향으로 회전할때 같은 모양이 나올 경우는 4개까지 나오지 않지요.

실제 문제를 푸는 코드는 아래에 있습니다. 

static int maxValue(int y,int x){
		int max=0;
		for(int next=0;next<19;next++){
			int r=shapes[next].length;
			int c=shapes[next][0].length;
			if(y+r>n||x+c>m) continue;
			int sum=0;
			for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
				sum+=map[i][j]*shapes[next][i-y][j-x];
			max=Math.max(max, sum);
		}
		return max;
	}

인자로 받은 y와 x는 비교할 위치를 말합니다. y는 세로축, x는 가로축의 좌표라고 보면 됩니다.

우리는 회전해서 나온 각각의 모양 19개(3차원 배열속의 2차원 배열 갯수)를 위에서 만들었지 않았나요? 그러니 for문을 19번 반복을 하는 겁니다.

이 for문 안에 r과 c는 만들었던 모양의 가로 길이, 세로 길이를 나타냅니다. 만약 {{ 0,1,0 }, { 1,1,1 }}의 (ㅗ)모양이라면 r의 값은 2, c의 값은 3이 되는 겁니다. 이런 길이가 입력 받은 보드의 범위를 넘어가게 되면 구할 필요가 없어지지요.

그런 조건을 if문으로 거릅니다.

int r=shapes[next].length;
int c=shapes[next][0].length;
if(y+r>n||x+c>m) continue;

범위 안에 있다면 이제 더해주면 됩니다. 우리가 블록이 있는 경우에는 1을 저장했었죠? 블록이 없는 경우는 0을 저장했었습니다. 그래서 판의 숫자에 이 이차원 배열을 단지 곱해주면 됩니다. 이 값을 모두 더하는 것이죠.

sum+=map[i][j]*shapes[next][i-y][j-x];

이제 모든 판의 좌표를 돌면서 가장 큰 값을 구하면 그게 답이 되는 겁니다. 전체 코드는 아래에 있습니다.

import java.util.Scanner;
public class Main {

	static int n,m;
	static int [][]map;
	static int [][][]shapes={
			{{1,1,1,1}},{{1},{1},{1},{1}}, 
			{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
			{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
			{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
			{{1,1},{1,1}},
			{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
			{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
	};
	public static void main(String[] ar){
		Scanner in=new Scanner(System.in);
		n=in.nextInt(); m=in.nextInt();
		map=new int[n][m];
		for(int i=0;i<n;i++) for(int j=0;j<m;j++)
			map[i][j]=in.nextInt();
		int max=0;
		for(int i=0;i<n;i++) for(int j=0;j<m;j++)
				max=Math.max(maxValue(i,j), max);
		System.out.println(max);
	}
	static int maxValue(int y,int x){
		int max=0;
		for(int next=0;next<19;next++){
			int r=shapes[next].length;
			int c=shapes[next][0].length;
			if(y+r>n||x+c>m) continue;
			int sum=0;
			for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
					sum+=map[i][j]*shapes[next][i-y][j-x];
			max=Math.max(max, sum);
		}
		return max;
	}
}

이상으로 테트로미노 문제를 풀어보았습니다.

14499번 주사위 굴리기

https://www.acmicpc.net/problem/14499

문제 해석

어떤 판 위에 주사위가 있습니다. 이 판에는 임의의 숫자가 적혀있습니다. 주사위를 입력받은 방향으로 굴리면서 주사위 윗면의 숫자를 조건에 따라 출력해주는 문제입니다. 규칙을 따져보자면 이렇습니다.

1. 처음 주사위의 모든 면에는 0이 쓰여있습니다. 그러니까 처음 6면에는 모두 0인 수가 적혀있는 것이죠.

2. 주사위가 굴러가면서 주사위 아랫면에 판의 숫자가 쓰여집니다. 단, 판의 숫자가 0일때는 주사위 윗면의 숫자를 출력해줍니다.

3. 만약 주사위가 판의 범위에서 나가는 입력이 들어왔을때는 깔끔하게 무시해주면 됩니다.

제약 조건

판의 가로(N), 세로(M) 크기는 1이상 20이하, 그리고 주사위를 어느 방향으로 굴릴지에 대한 입력은 1이상 1000이하로 들어옵니다. 주사위의 처음 위치는 판의 범위에 있어야하므로 좌표의 위치(x,y)는 0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1 입니다.

풀이

문제의 조건이 약간 이상하긴 합니다. 보통 x는 가로, y는 세로를 문제로 주고 역시 n도 세로의 길이, m도 가로의 길이로 주는게 조금 일반적이거든요.

그래서 저는 y를 세로 좌표, x를 가로 좌표로 두고 문제를 풀겠습니다.

우선 주사위를 어떻게 굴릴지 머리부터 굴려봅시다. 우선 전개도로 어떻게 주사위를 굴려볼까 봅시다. 

그림에서 가장 가운데 주사위의 전개도가 초기의 주사위입니다. 분홍색이 아랫면, 주황색이 윗면이라고 가정하지요. 주사위의 왼쪽면은 왼쪽 날개, 오른쪽 면은 오른쪽 날개라고 가정한다면 가운데의 주사위 전개도의 모든 면은 이렇게 되겠네요.

0번: 뒷면, 1번: 아랫면, 2번: 앞면, 3번: 윗면, 4번: 왼쪽면, 5번: 오른쪽면

그렇죠?

우리는 이것을 배열 인덱스로 생각해야합니다. 그러니 전개도의 숫자는 적혀져있는 숫자가 아니고 자리를 나타냅니다.

만약 이 상태에서 오른쪽으로 주사위를 굴린다면 0번 자리에 있던 수는 그대로 0번 자리에 있던 수가, 기존 1의 위치에는 5번의 자리에 있는 수가, 기존 2의 자리에는 그대로 2의 자리에 있던 수가, 기존 3의 자리에는 4의 자리에 있던 수가, 기존 4의 자리에는 1의 자리에 있던 수가, 기존 5의 자리에는 3의 자리에 있던 수가 됩니다. 숫자들이 자리를 찾아 이동하게 된것이죠.

정리하자면 이렇습니다.

이처럼 오른쪽으로 이동할때 5번째 자리에 있던 숫자는 1번째 자리로 이동하며, 4번째 자리에 있던 숫자는 3번째 자리로 이동합니다.

그렇게 위로 굴렸을때, 아래로 굴렸을때, 왼쪽으로 굴렸을때, 오른쪽으로 굴렸을때는 위의 그림의 전개도와 같습니다.

자, 이것을 이제 배열로 표현해보지요.

int dice[6];
int perm[5][6] = {
	{},
	{ 0,5,2,4,1,3 },{ 0,4,2,5,3,1 },
	{ 3,0,1,2,4,5 },{ 1,2,3,0,4,5 }
};

주어지는 입력에서 주사위를 굴릴때 동쪽은 1(오른쪽으로 굴릴 때), 서쪽은 2(왼쪽으로 굴릴 때), 북쪽은 3(위쪽으로 굴릴때), 남쪽은 4(아래쪽으로 굴릴 때) 이니까 그 순서대로 배열에 초기화했습니다. 0번은 동서남북으로 쓰여지 않으니 비어두었습니다.

그리고 dice라는 배열은 실제 주사위를 의미합니다. 여기에 주사위에 실제 적혀있는 숫자가 저장이 되죠.

이제 perm이라는 2차원 배열과 dice가 어떻게 동작하게 될까요? 우선 주사위 dice에는 다음과 같이 {5, 4, 3, 6, 8, 9}라는 수가 적혀져있다고 가정해보겠습니다. 이것을 오른쪽으로 굴리면 dice의 숫자는 어떻게 변할까요?

dice는 perm의 값의 따라 위치를 찾아 이동합니다. 오른쪽으로 이동할때 0번의 숫자는 0번으로, 5번의 숫자는 1번으로, 2번의 수는 2번으로, 4번의 수는 3번으로, 1번의 수는 4번으로, 3번의 수는 5번으로 이동하게 됩니다.

코드로 구현하면 이렇습니다.

void roll(int d) {
	int temp[6];
	for (int i = 0; i < 6; i++)
		temp[i] = dice[perm[d][i]];
	for (int i = 0; i < 6; i++)
		dice[i] = temp[i];
}

roll이라는 함수는 방향 d를 인자로 받습니다. 이렇게 d(1은 오른쪽, 2는 왼쪽, 3은 위쪽, 4는 아래쪽)에 따라서 perm을 결정하고 어떻게 dice를 배열할지를 정하게 됩니다. 

이를 토대로 이제 전체 문제를 풀면 됩니다.

int map[21][21], command[1001], n, m, k;
int perm[5][6] = {
	{},
	{ 0,5,2,4,1,3 },{ 0,4,2,5,3,1 },
	{ 3,0,1,2,4,5 },{ 1,2,3,0,4,5 }
};

int inc[5][2]{ {},{ 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
int dice[6];

void roll(int d) {
	int temp[6];
	for (int i = 0; i < 6; i++)
		temp[i] = dice[perm[d][i]];
	for (int i = 0; i < 6; i++)
		dice[i] = temp[i];
}


void solve(int next, int y, int x) {
	if (next == k) return;
	int dir = command[next];
	int Y = y + inc[dir][0], X = x + inc[dir][1];
	if (Y < 0 || Y >= n || X < 0 || X >= m) {
		solve(next + 1, y, x);
		return;
	}

	roll(dir);
	if (map[Y][X] == 0) map[Y][X] = dice[1];
	else {
		dice[1] = map[Y][X];
		map[Y][X] = 0;
	}
	printf("%d\n", dice[3]);
	solve(next + 1, Y, X);
}

solve라는 함수가 이제 문제를 푸는 재귀함수입니다. 인자 next는 다음 방향으로 이동하라는 인덱스입니다. 이것을 comand가 사용합니다.

command라는 배열은 어떻게 이동할지를 담고 있는 변수입니다. 동서남북 이동이 그것이죠. 동서남북 이동 입력이 1000개가 주어지니 command의 배열을 1000+1개로 잡아놓았습니다.

inc는 어떻게 주사위 위치를 증가할지를 담고 있는 변수입니다. inc는 방향에 따라서 (1,2,3,4) 1이이면 x축으로 1증가, 2이면 x축으로 1감소,.. 이런 식입니다.

solve함수에서 만일 범위 밖이면 다음 명령어를 실행하죠. 그것이 조건문에 걸려있군요. 조건에 걸리지 않았다면 주사위를 방향에 따라 굴리고, 이동했던 판의 숫자가 0이면 주사위의 아랫면의 숫자를 판에 복사하며 그것이 아니라면 판의 숫자를 주사위의 아랫면에 복사하고 그 판의 숫자를 0으로 바꾸어줍니다. 그 후 이제 윗면의 수 dice[3]을 출력하면 되지요.

전체 코드는 아래와 같습니다.

#include <cstdio>

using namespace std;
int map[21][21], command[1001], n, m, k;
int perm[5][6] = {
	{},
	{ 0,5,2,4,1,3 },{ 0,4,2,5,3,1 },
	{ 3,0,1,2,4,5 },{ 1,2,3,0,4,5 }
};

int inc[5][2]{ {},{ 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
int dice[6];

void roll(int d) {
	int temp[6];
	for (int i = 0; i < 6; i++)
		temp[i] = dice[perm[d][i]];
	for (int i = 0; i < 6; i++)
		dice[i] = temp[i];
}


void solve(int next, int y, int x) {
	if (next == k) return;
	int dir = command[next];
	int Y = y + inc[dir][0], X = x + inc[dir][1];
	if (Y < 0 || Y >= n || X < 0 || X >= m) {
		solve(next + 1, y, x);
		return;
	}

	roll(dir);
	if (map[Y][X] == 0) map[Y][X] = dice[1];
	else {
		dice[1] = map[Y][X];
		map[Y][X] = 0;
	}
	printf("%d\n", dice[3]);
	solve(next + 1, Y, X);
}

int main() {
	int y, x;
	scanf("%d %d %d %d %d", &n, &m, &y, &x, &k);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &map[i][j]);

	for (int i = 0; i < k; i++) scanf("%d", &command[i]);
	solve(0, y, x);
}