백준 - 무기공학

문제 설명

격자가 있는 칸에 부메랑(4가지 도형)을 형성하여 최댓값을 구하는 문제이다.

격자의 최대 칸이 5*5이므로 완탐해도 상관 없었다.

현재 위치하고 있는 칸을 부메랑의 중심부라 가정하고 부메랑을 형성하였다.

방문 여부를 판단하여 현재 위치에서 부메랑을 만들 수있는지 판별하였다.

풀이

static boolean v[][];

	// 부매랑들의 강도 합의 최댓값을 출력하시오
	public static int solution() {
		v = new boolean[n][m];
		pick(0, 0);
		return answer;
	}

	public static void pick(int cnt, int sum) {
		if (n * m <= cnt) {
			answer = Math.max(sum, answer);
			return;
		}
		// core
		int y = cnt / m;
		int x = cnt % m;

		if (v[y][x]) {
			pick(cnt + 1, sum);
		} else {
			v[y][x] = true;
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i][0];
				int nx = x + dx[i][0];

				if (isOutOfRange(ny, nx) || v[ny][nx])
					continue;

				int nny = y + dy[i][1];
				int nnx = x + dx[i][1];

				if (isOutOfRange(nny, nnx) || v[nny][nnx])
					continue;

				v[ny][nx] = true;
				v[nny][nnx] = true;

				pick(cnt + 1, sum + (tree[y][x] * 2) + tree[ny][nx] + tree[nny][nnx]);
				v[ny][nx] = false;
				v[nny][nnx] = false;
			}

			v[y][x] = false;
			pick(cnt + 1, sum);
		}

	}

	static boolean isOutOfRange(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= n || nx >= m;
	}