[자바] 백준 14500번: 테트로미노

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

14500번: 테트로미노

회전, 대칭까지 생각하면 폴리오미노가 총 19가지가 생기는데

이 모든것을 일일이 적어서 하기에는 너무 힘들것같았다.

문제에서 가능한 폴리오미노가 5종류 있다고 해서 이 5종류를 어떻게 손봐야할까...생각하던 찰나

그냥 폴리오미노에 대한 조건을 가지고 백트래킹을 하면 될 것 같았다.

 

백트래킹으로 풀고 나서 확인해보니 값이 틀렸다.

왜 틀렸는지 visited를 출력해서 보니

"ㅗ"모양을 만들 수가 없어서 그랬던 것이다. 

(매번 끄트머리에서 상하좌우로 늘여가기 때문에)

 

그래서 ㅗ까지 만들기 위해서

지금까지 선택한 칸들을 하나씩 꺼내서 그 칸에서 상하좌우로 블럭을 이어나가도록 했다.

그랬더니 시간초과가 났다.

 

아래는 시간초과가 난 코드

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

public class P14500 {

	static int[][] board;
	static boolean[][] visited;
	static int result, sum;
	static int[] dx = { 0, 0, -1, +1 };
	static int[] dy = { -1, +1, 0, 0 };
	static int n, m;
	static Stack<Integer[]> points = new Stack<>();

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		board = new int[n][m];
		visited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				Integer[] start = { i, j };
				points.push(start);
				visited[i][j] = true;
				sum = board[i][j];
				perm(i, j, 1, 4);
				visited[i][j] = false;

				points.pop();
			}
		}

		System.out.println(result);

	}

	static void perm(int r, int c, int i, int k) {

		if (i == k) {
			if (result < sum) {
				result = sum;

			}
			return;
		}

		for (int p = 0; p < points.size(); p++) {
			int now_r = points.get(p)[0];
			int now_c = points.get(p)[1];

			for (int z = 0; z < 4; z++) {
				// 상하좌우 4방향 탐색
				int next_c = now_c + dx[z];
				int next_r = now_r + dy[z];

				if (next_c < 0 || next_c > m - 1 || next_r < 0 || next_r > n - 1)
					continue;

				if (visited[next_r][next_c] == true)
					continue;

				visited[next_r][next_c] = true;
				sum += board[next_r][next_c];
				Integer[] next_xy = { next_r, next_c };
				points.push(next_xy);

				perm(next_r, next_c, i + 1, n);

				points.pop();
				visited[next_r][next_c] = false;
				sum -= board[next_r][next_c];
			}
		}

	}
}

새로 코드를 짜는데 진짜 귀신이 곡할노릇

count가 1씩 증가하고 4가되면 return하는데

도대체 왜 카운트가 5가 돼있고 if(count==4)에서 걸려서 출력이 되고있는거지;;

 

k는 4로 줬고 코드에서 k가 증가할 일이 없는데 도대체 왜 k가 5가 된건지 진짜 울고싶음

 

알고보니 변수k를 원래는 n으로 썼는데 처음 입력받는 n이랑 변수명이 겹쳐서 k로 바꿨었고

그 이후로 perm 재귀 돌릴때 n으로써놨던걸 k로 써야했는데 안 고쳤던게 문제였음.

컴퓨터 사탄들린줄 알았는데 내가 사탄이었음.

그래서 어떻게 해야 백트래킹을 쓰면서 ㅗ모양도 찾을 수 있을까 한참 고민하다가

구글링을 했는데

정말 획기적인 코드를 발견했다.

 

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

public class P14500 {

	static int[][] board;
	static boolean[][] visited;
	static int result, sum;
	static int[] dx = { 0, 0, -1, +1 };
	static int[] dy = { -1, +1, 0, 0 };
	static int n, m;

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

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		board = new int[n][m];
		visited = new boolean[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < m; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visited[i][j] = true;
				sum = board[i][j];
				perm(i, j, 1, 4);
				visited[i][j] = false;

			}
		}

		System.out.println(result);

	}

	static void perm(int r, int c, int count, int k) {

		if (count == k) {
			if (result < sum) {
				result = sum;

			}
			return;
		}

		for (int z = 0; z < 4; z++) {
			// 상하좌우 4방향 탐색
			int next_c = c + dx[z];
			int next_r = r + dy[z];

			if (next_c < 0 || next_c > m - 1 || next_r < 0 || next_r > n - 1)
				continue;

			if (visited[next_r][next_c] == true)
				continue;

			if (count == 2) {
				visited[next_r][next_c] = true;
				sum += board[next_r][next_c];

				perm(r, c, count + 1, k);

				visited[next_r][next_c] = false;
				sum -= board[next_r][next_c];

			}
			visited[next_r][next_c] = true;
			sum += board[next_r][next_c];

			perm(next_r, next_c, count + 1, k);

			visited[next_r][next_c] = false;
			sum -= board[next_r][next_c];
		}
	}

}

코드를 보면 if(count==2)가 보일 것이다.

ㅗ모양을 만들기 위해서는 count==2일때, 즉 두 칸 만들어 놨을 때 두 갈래로 가야하는데

if문 안의 perm을 보면 첫번째,두번째 인자로 next_r, next_c를 넣지 않고 그냥 r,c를 넣었다.

그러면 다음블럭을 선택한 다음 그 블럭으로 가서 또 다음블럭을 선택하는게 아니라

다음블럭을 선택한 다음 현재위치에서 또 다음블럭을 선택하게 되는것이다.