테트로미노 [BOJ 14500]

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라. 

- 문제가 무엇인가?

-> 

    

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

[내 코드]

import java.util.*; 


public class Main {
    
    public static int N;
    public static int M;
    public static int maxSum; 
    public static int[][] map;
    public static boolean[][] visited; 
    
    
    public static int[] dx = {0, -1, 0, 1};
    public static int[] dy = {1, 0, -1, 0};
    
    public boolean isInside(int x, int y){
        if(1<=x && x<=N && 1<=y && y<=M){
            return true;
        }else{
            return false; 
        }
    }
    
    
    
    
    
    public void type1And3And4(int x, int y, int cnt, ArrayList<Integer> arr, int sum){
        
        
        
            if(cnt == 3){
                
                StringBuilder sb = new StringBuilder();
                
                for(int i=0; i<arr.size(); i++){
                    sb.append(arr.get(i).toString());
                }
                
                String str = sb.toString();
                
                if(str.equals("000") || str.equals("111") || str.equals("222") || str.equals("333")){
                    maxSum = Math.max(maxSum, sum);
                }
                
                if(str.equals("232") || str.equals("323") || str.equals("030") || str.equals("303") || str.equals("010") || str.equals("101") || str.equals("121") || str.equals("212")){
                    maxSum = Math.max(maxSum, sum);
                }
                
                if(str.equals("011") || str.equals("001") || str.equals("100") || str.equals("110")){
                    maxSum = Math.max(maxSum, sum);
                }
                
                if(str.equals("211") || str.equals("112") || str.equals("221") || str.equals("122")){
                    maxSum = Math.max(maxSum, sum);
                }
                
                if(str.equals("300") || str.equals("003") || str.equals("033") || str.equals("330")){
                    maxSum = Math.max(maxSum, sum);
                }
                
                
                if(str.equals("233") || str.equals("223") || str.equals("332") || str.equals("322")){
                    maxSum = Math.max(maxSum, sum);
                }
                
                
                
                return; 
                
            }    
                
        
            
            
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(isInside(nx,ny) && visited[nx][ny] == false){
                    visited[nx][ny] = true;
                    arr.add(i);
                    type1And3And4(nx, ny, cnt+1, arr, sum+map[nx][ny]);
                    arr.remove(arr.size()-1);
                    visited[nx][ny] = false;
                    
                }
            }
        
        
        
        
    }
    
    
    public void type2(int x, int y){
        
        int sum = 0;
        
        
        if(isInside(x+1,y) && isInside(x, y+1) && isInside(x+1, y+1)){
            sum = map[x][y] + map[x+1][y] + map[x][y+1] + map[x+1][y+1];
        }
        
        
        maxSum = Math.max(maxSum, sum);
        
        
    }
    
    
    public void type5(int x, int y){
        
        int sum1 = 0;
        int sum2 = 0;
        int sum3 = 0;
        int sum4 = 0;
        
        
        if(isInside(x+1,y) && isInside(x, y+1) && isInside(x-1, y)){
            sum1 = map[x][y] + map[x+1][y] + map[x][y+1] + map[x-1][y];
        }
        
        if(isInside(x+1,y) && isInside(x, y+1) && isInside(x, y-1)){
            sum2 = map[x][y] + map[x+1][y] + map[x][y+1] + map[x][y-1];
        }
        
        
        if(isInside(x+1,y) && isInside(x, y-1) && isInside(x-1, y)){
            sum3 = map[x][y] + map[x+1][y] + map[x][y-1] + map[x-1][y];
        }
        
        
        if(isInside(x,y+1) && isInside(x, y-1) && isInside(x-1, y)){
            sum4 = map[x][y] + map[x][y+1] + map[x][y-1] + map[x-1][y];
        }
        
        
        
        
        
        
        maxSum = Math.max(maxSum, sum1);
        maxSum = Math.max(maxSum, sum2);
        maxSum = Math.max(maxSum, sum3);
        maxSum = Math.max(maxSum, sum4);
        
    }
    
    
    
    
    
    public static void main(String args[]) {
      Main T = new Main();
      Scanner sc = new Scanner(System.in);
      
      
      N = sc.nextInt();
      M = sc.nextInt();
      
      map = new int[N+10][M+10];
      visited = new boolean[N+10][M+10];
      
      maxSum = Integer.MIN_VALUE; 
      
      
      for(int i=1; i<=N; i++){
          for(int j=1; j<=M; j++){
              map[i][j] = sc.nextInt();
          }
      }
      
      
      for(int i=1; i<=N; i++){
          for(int j=1; j<=M; j++){
              
              ArrayList<Integer> arr1 = new ArrayList<>();
              T.type1And3And4(i,j, 0, arr1, map[i][j]);
              T.type2(i,j);
              T.type5(i,j); 
              
              
          }
      }
      
      
      System.out.println(maxSum);
      
      
      
      
    }
}

[참고 코드]

import java.util.*;

public class Main {
    
    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][] visited; 
    public static int maxSum;
    
    
    public boolean isInside(int x, int y){
        if(1<=x && x<=N && 1<=y && y<=M){
            return true;
        }else{
            return false; 
        }
    }
    
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    
    
    public void DFS(int x, int y, int sum, int cnt){
        
        if(cnt == 4){
            maxSum = Math.max(maxSum, sum);
            return; 
        }
        
        
        
        for(int i=0; i<4; i++){
            
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(!isInside(nx, ny)){
                continue;
            }
            
            
            if(visited[nx][ny] == false){
                
                  
                if(cnt == 2){
                    visited[nx][ny] = true;
                    DFS(x, y, sum+map[nx][ny], cnt+1); 
                    visited[nx][ny] = false;
                }
            
            
                visited[nx][ny] = true;
                DFS(nx, ny, sum+map[nx][ny], cnt+1);
                visited[nx][ny] = false; 
            
                
                
                
            }
            
          
            
            
        }
        
        
    }
    
    
    public static void main(String args[]) {
      Main T = new Main();
      Scanner sc = new Scanner(System.in);
      
      N = sc.nextInt();
      M = sc.nextInt();
      maxSum = Integer.MIN_VALUE;
      
      map = new int[N+10][M+10];
      visited = new boolean[N+10][M+10];
      
      for(int i=1; i<=N; i++){
          for(int j=1; j<=M; j++){
              map[i][j] = sc.nextInt();
          }
      }
      
      
      for(int i=1; i<=N; i++){
          for(int j=1; j<=M; j++){
              visited[i][j] = true;
              T.DFS(i, j, map[i][j], 1);
              visited[i][j] = false; 
          }
      }
      
      
      System.out.println(maxSum); 
      
      
      
      
      
      
      
      
    }
}

 

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?

-> 참고 코드를 통해서 코드 길이를 50%줄이고, 코드 시간도 50%줄일 수 있었다

-> 아이디어를 갖는 것이 중요하다

-> DFS로 탐색이 가능하고, 중요한 것은 ㅗ 모양에 대해서도 DFS에서 탐색이 가능하다

-> 탐색을 하는 방법은, 값만 더해주고, 탐색 위치는 그대로 가져가는 것이다.

-> 단, 탐색을 할 때, visited[nx][ny] == false라는 조건을 만족해야 한다는 점을 기억하자.