BEAKJOON / 백준 - JAVA 14500번 테트로미노

2024.07.08기준 - 골드4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 5개의 테트로미노가 주어질 지며 회전, 반전이 가능할 때, 하나의 블럭만 사용해서 종이 위에 올려 가려지는 숫자 합이 가장 큰 값을 출력하는 문제입니다.

 

1. 일단 저의 접근은 경우의 수를 전부 계산해 보았습니다.

2. 주어진 경우의 수로 총 57가지의 이동 좌표가 나왔고, 이동 좌표를 저장해 주었습니다.

static int[] dx = {1, 2, 3, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 1, 1, 1, 1, 2, 2, 0, 0, -1, 0, 1, 2, 1, 0, 0, 1, 2, 2, 0, 1, 1, 1, 1, 2, 0, -1, -1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 0, 1, 0};
static int[] dy = {0, 0, 0, 1, 2, 3, 0, 1, 1, 1, 2, 2, 0, 0, 1, 0, 1, 2, 0, 0, -1, 1, 2, 2, 1, 1, 1, 0, 1, 2, 0, 0, 1, 1, 1, 2, 0, -1, -1, 1, 1, 2, 0, 1, 1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 1, 2};

 

3. 입력받은 종이 위의 수를 저장하고 저장된 위치별로 도형의 모형대로 체크를 해주었습니다.

for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        function(i, j);
    }
}

위치 별로 함수 호출

// 테트로미노 범위 안에 최대 값을 구하는 함수.
private static void function(int y, int x) {
    int nowy = y;
    int nowx = x;
    int nexty, nextx;
    int sum = map[y][x];

    for (int i = 0; i < 57; i++) {
        nexty = nowy + dy[i];
        nextx = nowx + dx[i];

        if (check(nexty, nextx)) {
            sum += map[nexty][nextx];

            if (i % 3 == 2) {
                max = Math.max(max, sum);
                sum = map[y][x];
            }
        } else {
            if (i % 3 == 0) {
                i += 2;
            } else if (i % 3 == 1) {
                i++;
            }

            sum = map[y][x];
        }
    }
}

// 참조하는 좌표가 범위 안에 있는지 확인하는 함수.
private static boolean check(int y, int x) {
    return y >= 0 && x >= 0 && y < h & x < w;
}

 

1. 함수를 호출한 현제 좌표 y, x를 통해 이동할 좌표 57가지를 계산합니다.
2. check 함수를 통해 종이 위를 벗어나지 않도록 체크해줍니다.
3. 벗어나지 않다면 sum 변수에 합을 더 해 가며 (i % 3) == 2가 되면 하나의 도형이 완성되어 max값을 확인합니다.
4. 만약 종이 위를 벗어난다면 상황에 맞게 다음 도형으로 넘어가기 위해 참조하는 인덱스를 조정해줍니다.

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static int[] dx = {1, 2, 3, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 1, 1, 1, 1, 2, 2, 0, 0, -1, 0, 1, 2, 1, 0, 0, 1, 2, 2, 0, 1, 1, 1, 1, 2, 0, -1, -1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 2, 0, 1, 0};
	static int[] dy = {0, 0, 0, 1, 2, 3, 0, 1, 1, 1, 2, 2, 0, 0, 1, 0, 1, 2, 0, 0, -1, 1, 2, 2, 1, 1, 1, 0, 1, 2, 0, 0, 1, 1, 1, 2, 0, -1, -1, 1, 1, 2, 0, 1, 1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 1, 2};
	static int h, w, max = 0;
	static int[][] map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		h = Integer.parseInt(st.nextToken());
		w = Integer.parseInt(st.nextToken());
		
		map = new int[h][w];
		for (int i = 0; i < h; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < w; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				function(i, j);
			}
		}
		
		bw.write(Integer.toString(max));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 테트로미노 범위 안에 최대 값을 구하는 함수.
	private static void function(int y, int x) {
		int nowy = y;
		int nowx = x;
		int nexty, nextx;
		int sum = map[y][x];
		
		for (int i = 0; i < 57; i++) {
			nexty = nowy + dy[i];
			nextx = nowx + dx[i];
			
			if (check(nexty, nextx)) {
				sum += map[nexty][nextx];
				
				if (i % 3 == 2) {
					max = Math.max(max, sum);
					sum = map[y][x];
				}
			} else {
				if (i % 3 == 0) {
					i += 2;
				} else if (i % 3 == 1) {
					i++;
				}
				
				sum = map[y][x];
			}
		}
	}
	
	// 참조하는 좌표가 범위 안에 있는지 확인하는 함수.
	private static boolean check(int y, int x) {
		return y >= 0 && x >= 0 && y < h & x < w;
	}
}