백준 14500 - 테트로노미노

문제 설명

 

 

 다른 사람들의 코드에 비해서 빠르다거나 메모리를 효율적으로 사용한 것은 아니지만, 쉽게 이해 할 수 있는 코드라고 생각하게되어 포스팅을 하게되었습니다.

 

기본적인 개념은, https://www.acmicpc.net/problem/14503 백준 14503번 로봇청소기로부터 따왔습니다.

 

알고리즘은 이렇습니다. 해당 도형을 y축 대칭시켜서 나온 모양이 원래 모양과 다르지 않다면, 동서남북 각 방향으로 도형을 그리게 되면 모든 경우의 수를 나열 할 수 있게 됩니다. 모양이 다른 경우, y축 대칭 시킨 도형에대한 메소드를 하나 더 만들어줘야 합니다.

 

y축 대칭시킨 후에도 모양이 같은 경우(메소드 1개)

y축 대칭 시킨 후에 모양이 변하는 경우(메소드 2개)

※ Y축 대칭해서 달라지는 도형들은 h와 ㄱ 도형입니다.

해당 코드를 이해하기 위해서는 메소드, 변수별 역할만 숙지하면 됩니다.

 

변수

x, y int 변수 : 현재 위치를 나타내는 좌표

direction : 현재 바라보는 방향을 나타내는 변수 // 0 : 북쪽, 1 : 동쪽, 2 : 남쪽, 3: 서쪽

그리기 메소드

answer : 해당 도형만큼 이동하면서 사용하는 누적 값(답 도출에 사용됨)

step : 한칸 전진합니다. 전진하기 전에, 전진 할 좌표가 배열 인덱스를 벗어날 경우 x,y 좌표를 1001로 고정시킵니다.(좌표 입력의 최댓값이 1000이기 때문에, 이렇게 예외처리)

turn_left : 방향 값을 연산해줍니다. 왼쪽으로 돕니다.

turn_right : 방향 값을 연산해줍니다. 오른쪽으로 돕니다.

 

이 세 메소드를 사용해서, 도형 4칸을 그려나간다고 생각하면 됩니다. 다만, 시작 위치는 이미 정해져 있으므로 해당 위치는 빼고 생각합니다. 모든 도형 그리기 메소드는 각각 step 메소드를 세번 실행하게 됩니다.(한 칸은 시작 위치이므로 이미 그렸다고 생각)

 

 

도형 메소드

막대

박스

ㄱ

h

ㅗ

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

public class Main {
    public static int[] step(int[][] map, int x, int y, int direction, int answer){
        if(!Arrays.equals(new int[]{1001, 1001}, new int[]{x, y})){
            if(direction == 0) {
                if (0 <= x - 1) return new int[]{x - 1, y, answer + map[x - 1][y]};
                else return new int[]{1001, 1001, 0};
            } else if(direction == 1) {
                if (map[x].length > y + 1) return new int[]{x, y + 1, answer + map[x][y + 1]};
                else return new int[]{1001, 1001, 0};
            } else if(direction == 2) {
                if (map.length > x + 1) return new int[]{x + 1, y, answer + map[x + 1][y]};
                else return new int[]{1001, 1001, 0};
            } else {
                if (0 <= y - 1) return new int[]{x, y - 1, answer + map[x][y - 1]};
                else return new int[]{1001, 1001, 0};
            }
        } else return new int[]{1001, 1001, 0};
    }
    public static int turn_left(int direction){
        if(direction == 0){
            return 3;
        } else return direction - 1;
    }
    public static int turn_right(int direction){
        if(direction == 3){
            return 0;
        } else return direction + 1;
    }
    public static int first(int[][] map, int x, int y, int direction, int answer){ // 막대
        int[] cord = new int[]{x, y, answer + map[x][y]};
        for(int i=0;i<3;i++){
            if (Arrays.equals(cord, new int[]{1001, 1001})){
                return 0;
            } else cord = step(map, cord[0], cord[1], direction, cord[2]);
        }
        return cord[2];
    }
    public static int second(int[][] map, int x, int y, int direction, int answer){ // 박스
        int[] cord = new int[]{x, y, answer + map[x][y]};
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction = turn_right(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction = turn_right(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        return cord[2];
    }
    public static int third(int[][] map, int x, int y, int direction, int answer){ // h
        int[] cord = new int[]{x, y, answer + map[x][y]};
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction = turn_left(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction = turn_right(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        return cord[2];
    }
    public static int third_two(int[][] map, int x, int y, int direction, int answer){ // h
        int[] cord = new int[]{x, y, answer + map[x][y]};
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction = turn_right(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction = turn_left(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        return cord[2];
    }
    public static int fourth(int[][] map, int x, int y, int direction, int answer){ // ㄱ
        int[] cord = new int[]{x, y, answer + map[x][y]};
        for(int i=0;i<2;i++){
            cord = step(map, cord[0], cord[1], direction, cord[2]);
        }
        direction = turn_left(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        return cord[2];
    }
    public static int fourth_two(int[][] map, int x, int y, int direction, int answer){ // ㄱ
        int[] cord = new int[]{x, y, answer + map[x][y]};
        for(int i=0;i<2;i++){
            cord = step(map, cord[0], cord[1], direction, cord[2]);
        }
        direction = turn_right(direction);
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        return cord[2];
    }
    public static int fifth(int[][] map, int x, int y, int direction, int answer){ // ㅗ
        int[] cord = new int[]{x, y, answer + map[x][y]};
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        int[] temp = cord;
        int direction2 = direction;
        int answer2;
        answer2 = answer;
        int answer3;
        answer3 = answer;
        cord = step(map, cord[0], cord[1], direction, cord[2]);
        direction2 = turn_right(direction2);
        temp = step(map, temp[0], temp[1], direction2, answer2);
        return temp[2] + cord[2] - answer3;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        ArrayList<Integer> possibles = new ArrayList<>();
        int N = Integer.parseInt(inputs[0]);
        int M = Integer.parseInt(inputs[1]);
        int[][] map = new int[N][M];
        // 0 - 북, 1 - 동, 2 - 남, 3 - 서
        for(int i=0;i<N;i++){
            map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        for(int i=0;i<map.length;i++){
            for(int j=0;j<map[i].length;j++){
                for(int z=0;z<4;z++){
                    possibles.add(first(map, i, j, z, 0));
                    possibles.add(second(map, i, j, z, 0));
                    possibles.add(third(map, i, j, z, 0));
                    possibles.add(third_two(map, i, j, z, 0));
                    possibles.add(fourth(map, i, j, z, 0));
                    possibles.add(fifth(map, i, j, z, 0));
                    possibles.add(fourth_two(map, i, j, z, 0));
                }
            }
        }
        System.out.println(Collections.max(possibles));
    }
}