Inor

[백준] 14500번 테트로미노 본문

Algorithm/백준

[백준] 14500번 테트로미노

Inor 2017. 11. 6. 14:29

 테트로미노 문제는 2차원 배열에 테트리스 게임에서 나오는 막대 모양을 올려 놨을때 해당 위치의 값들을 더해서 최댓값을 찾아내는 문제 입니다. 테트리스에 나오는 막대 모양은 회전, 대칭이 가능하다고 문제에서 설명해주고 있습니다. 해당 문제는 DFS를 이용해서 풀었습니다. 모든 막대기를 만드는 블록들이 총 4개라는 공통점을 찾았고 4번씩 이동했을때 모든 테트리스의 막대기 모양이 만들어진다는 것을 직접 그려가며 발견하였습니다. 4번 이동했을 경우에 1번, 2번, 3번, 4번째에 탐색된 위치의 값들을 더해서 최댓값과 비교하였습니다. 그러나 여기서 한가지 예외 상황이 있었는데 ㅗ모양의 막대기는 DFS를 이용해서 해결할 수 없다는 문제를 발견하였습니다. 이유는 중간에 3갈래 길이 생기는데 재귀함수를 이용해서 모든 위치를 탐색하는 것이 어렵다는 것을 발견하였습니다. 그래서 나머지 모양은 dfs()로 ㅗ 모양은 otherShapeCheck() 함수로 분리하였습니다. ㅗ 모양은 현재 처음 시작 위치에서 4방향(동, 서, 남, 북)을 모두 확인하여 중앙 포함 5곳의 위치에서 최솟값을 뺀 4개의 값을 더해서 최댓값과 비교하도록 만들었습니다. 아래는 문제와 소스 코드 입니다.


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


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Tetromino {

	int row, col;
	int[] dRow = { 0, 0, -1, 1 };
	int[] dCol = { -1, 1, 0, 0 };
	int[][] map;
	boolean[][] visit;
	int max = 0;

	void dfs(int n, int sRow, int sCol, int sum) {
		int nRow, nCol;

		if (n == 4) {
			sum += map[sRow][sCol];
			if (sum > max) {
				max = sum;
			}
			return;
		}
		visit[sRow][sCol] = true;
		for (int i = 0; i < 4; i++) {
			nRow = sRow + dRow[i];
			nCol = sCol + dCol[i];
			if (0 <= nRow && nRow < row && 0 <= nCol && nCol < col && visit[nRow][nCol] == false) {
				dfs(n + 1, nRow, nCol, sum + map[sRow][sCol]);
			}
		}
		visit[sRow][sCol] = false;
	}

	void otherShapeCheck(int sRow, int sCol) {
		int nRow, nCol;
		int sum = map[sRow][sCol];
		int n = 0;
		ArrayList<Integer> values = new ArrayList<Integer>();

		for (int i = 0; i < 4; i++) {
			nRow = sRow + dRow[i];
			nCol = sCol + dCol[i];
			if (0 <= nRow && nRow < row && 0 <= nCol && nCol < col) {
				values.add(map[nRow][nCol]);
			}
		}
		
		Collections.sort(values);
		if (values.size() >= 3) {
			for (int i = values.size() - 1; i >= 0; i--) {
				if (n++ == 3){
					break;
				}
				sum += values.get(i);
			}
		}
		
		if (sum > max){
			max = sum;
		}
		
	}

	void solve() {
		Scanner sc = new Scanner(System.in);

		row = sc.nextInt();
		col = sc.nextInt();
		map = new int[row][col];
		visit = new boolean[row][col];
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				map[i][j] = sc.nextInt();
			}
		}

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				dfs(1, i, j, 0);
				otherShapeCheck(i, j);
			}
		}

		System.out.println(max);
	}

	public static void main(String[] args) {
		Tetromino m = new Tetromino();
		m.solve();

	}

	class Pair<X, Y> {
		X x;
		Y y;

		public Pair(X x, Y y) {
			this.x = x;
			this.y = y;
		}

	}

}



'Algorithm > 백준' 카테고리의 다른 글

[백준] 5427번 불  (0) 2017.11.06
[백준] 2468번 안전 영역  (0) 2017.11.06
[백준] 7576번 토마토  (0) 2017.11.06
[백준] 14502번 연구소  (0) 2017.11.06
[백준] 14503번 로봇 청소기  (3) 2017.11.06
Comments