BOJ 3678

21 Sep 2020 • ProblemSolving

카탄의 개척차

문제출처

문제 해석

정해진 조건에 따라서 타일을 채운 후, n번째로 채운 타일에 어떤 자원을 선택하는지 고르는 문제입니다.

먼저, 게임판의 중앙에서 만들기 시작하고 나선형태로 진행합니다.

다음의 조건에 따라서 타일을 채워나갑니다.

  1. 새로운 타일은 이미 채워진 타일에 들어있는 자원과 다른 자원이어야 한다.
  2. 가능한 자원이 여러가지인 경우, 보드에 가장 적게 나타난 자원을 선택한다.
  3. 그러한 경우가 여러가지라면, 번호가 작은 것을 선택한다.

설계(20)

n<=10,000이고, 테스트케이스 c <=200이므로 단순 구현으로 문제풀이가 가능할 것으로 보입니다.

n이 최대 10000이 나와야 하므로 100x100의 공간이 필요할 것으로 보였습니다. 하지만 나선형태로 타일을 채우는 것을 구현하기 위해서 육각형모양으로 이동을 시켜줘야했기 때문에 두배가량의 공간에 여유를 주어서 기본 배열로 사용하였습니다(250x250)

움직일 수 있는 경우는 총 6가지로 육각형모양을 따릅니다. 처음 2->3으로 넘어갈 때에는 특수하게 위로 올라가는 방향을 포함하지않으므로 따로 예외처리를 해주어야 합니다.

또한, 각 자원이 얼마나 사용되었는지 파악하기 위해서 cnt라는 배열을 사용하였습니다.

어떤 자원을 선택하는지에 대한 함수 check(x,y)는 다음의 과정을 거칩니다.

  1. 주변 6방향의 타일이 가지고 있는 자원에 대한 정보를 boolean 배열에 저장해 놓습니다.
  2. boolean 배열이 체크가 안된 자원 중에서 적게 사용한 자원을 찾아줍니다.

두번째로 방향을 언제 틀어야하는지에 대한 함수 is_possible(x,y)는 다음 과정을 거칩니다.

  1. 주변 6방향에 자원이 몇개 채워졌는지 확인합니다.
  2. 규칙을 보면 주변 자원이 2개 이하인 경우 방향을 틀어주는 방식으로 되어있습니다. 이를 이용하여 boolean 형태로 리턴해주어 방향 변화 유무를 판단합니다.

타일을 채우는 시간을 포함하여 O(5x10000x200)=O(10^7)로 시간안에 풀이가 가능합니다.

구현(35)

코드(c++)
#include <iostream>
#include <cstring>

using namespace std;

#define MAXN 250
#define INF 987654321

int arr[MAXN][MAXN];
int dx[] = { -1,-2,-1,1,2,1 };
int dy[] = { 2,0,-2,-2,0,2 };
int cnt[6];
int c, n;
int check(int x, int y) {
	bool flag[6] = { false, };
	for (int i = 0; i < 6; i++) {
		flag[arr[x + dx[i]][y + dy[i]]] = true;
	}
	int min_v = INF;
	int num = 0;
	for (int i = 1; i < 6; i++) {
		if (!flag[i]) {
			if (cnt[i] < min_v) {
				min_v = cnt[i];
				num = i;
			}
		}
	}
	return num;
}
bool is_possible(int x, int y) {
	int tmp = 0;
	for (int i = 0; i < 6; i++) {
		if (arr[x + dx[i]][y + dy[i]]) tmp++;
	}
	return tmp > 2;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> c;
	while (c--) {
		memset(arr, 0, sizeof(arr));
		memset(cnt, 0, sizeof(cnt));
		cin >> n;
		int sx = 125;
		int sy = 125;
		int dir = 0;
		int num = 1;
		while (num <= n) {
			arr[sx][sy] = check(sx, sy);
			if (num == n) {
				cout << arr[sx][sy] << "\n";
				break;
			}
			cnt[arr[sx][sy]]++;
			sx += dx[dir];
			sy += dy[dir];
			num++;
			if (!is_possible(sx, sy)) {
				dir++;
				if (num < 5 && dir == 1) dir++;
				if (dir > 5) dir = 0;
			}
		}
		
	}
}
코드(python)
c = int(input())
dx = [-1,-2,-1,1,2,1]
dy = [2,0,-2,-2,0,2]
def check(x, y):
    flag = [False for x in range(6)]
    for i in range(6):
        flag[arr[x+dx[i]][y+dy[i]]]=True
    min_v_ = 987654321
    tmp_ = 0
    for i in range(1,6):
        if flag[i]==False:
            if cnt[i]<min_v_:
                min_v_ = cnt[i]
                tmp_ = i
    return tmp_
def is_possible(x,y):
    tmp_ = 0
    for i in range(6):
        if arr[x+dx[i]][y+dy[i]]>0:
            tmp_+=1
    return tmp_ > 2

for i in range(c):
    n = int(input())
    arr = [[0 for x in range(250)] for y in range(250)]
    cnt = [0 for x in range(6)]
    num = 1
    sx = 125
    sy = 125
    dir = 0
    while num < n:
        arr[sx][sy] = check(sx,sy)
        cnt[arr[sx][sy]]+=1
        sx += dx[dir]
        sy += dy[dir]
        num+=1
        if not is_possible(sx,sy):
            dir+=1
            if num<5 and dir == 1:
                dir+=1
            if dir>5:
                dir = 0
    print(check(sx,sy))
디버깅

디버깅을 하는데 시간이 오래걸렸습니다.

방향을 틀어주는 로직을 설계할 때 생각하지 못했습니다.

제출결과

16 ms (c++) 644 ms (pypy3)

마무리

단순 구현문제였지만 생각보다 까다로운 문제였습니다.

로직을 미리 설계하고 코드를 작성하는데도 생각치 못한 부분이 계속 드러납니다.

이런 실수가 반복되면 디버깅 시간이 늘어나고 결과적으로 안좋은 상황을 초래할 수 있을 것입니다.

설계하는 시간을 더 늘려서 꼼꼼히 체크해야할 것 같습니다.

 BOJ  NWERC2009

Related Posts