삼성 SW 역량 테스트 기출 문제 : 테트로미노

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

14500번: 테트로미노

// 코드

import java.util.*;
import java.io.*;
 
public class Main{
  
  static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  static int N, M;
  static int[][] myArr;
  static boolean [][]visited;
  static int maxSum;
  
  public static void main(String[] args) throws Exception {
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    
    myArr = new int[N][M];
    
    for(int i=0; i<N; i++) {
      st = new StringTokenizer(br.readLine());
      for(int j=0; j<M; j++) {
        myArr[i][j] = Integer.parseInt(st.nextToken());
      }
    }
    
    visited = new boolean[N][M];
    
    for(int r=0; r<N; r++) {
      for(int c=0; c<M; c++) {
        visited[r][c] = true;
        // 'ㅜ'를 제외한 나머지 경우는 DFS로 탐색
        dfs(r, c, 1, myArr[r][c]);
        // 'ㅜ'는 별도로 처리
        maxSum = Math.max(getLast(r, c), maxSum);
        visited[r][c] = false;
      }
    } 
    System.out.println(maxSum);
  }
  
  static void dfs(int row, int col, int cnt, int sum) {
    
    if(cnt >= 4) {
      maxSum = Math.max(maxSum, sum);
      return;
    } else {
      for(int d=0; d<dirs.length; d++) {
        int nr = row + dirs[d][0];
        int nc = col + dirs[d][1];
        
        if((0<=nr&&nr<N) && (0<=nc&&nc<M) && !visited[nr][nc]) {
          visited[nr][nc] = true;
          dfs(nr, nc, cnt+1, sum + myArr[nr][nc]);
          visited[nr][nc] = false;
        }
        
      } 
    }
  }
  
  static int getLast(int row, int col) {
    int base = myArr[row][col];
    int cnt  = 0; // 4방탐색의 성공횟수
    int min = Integer.MAX_VALUE;
    // 중심점을 중심으로 사방 탐색
    for(int d=0; d<dirs.length; d++) {
      int nr = row + dirs[d][0];
      int nc = col + dirs[d][1];
      
      if((0<=nr&&nr<N) && (0<=nc&&nc<M)) {
        cnt++;
        base += myArr[nr][nc];
        min = Math.min(min, myArr[nr][nc]);
      }
    }
    
    // 4방 탐색이 4군데 다 성공했다면 최솟값을 빼주기
    if(cnt == 4) {
      return base - min;
    } else if(cnt == 3) { // 3방향만 성공했다면 그대로 진행
      return base;
    } else { // 나머지 경우는 모양 만들기 실패
      return -1;
    }
    
  }
  
}

 

// 복습

import java.util.*;
import java.io.*;
 
public class Main{
  
  // 상, 하, 좌, 우
  static final int[][] DELTAS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  static int N, M;
  static int[][] arr;
  static boolean[][] visited;
  static int mySum = Integer.MIN_VALUE; // 답
  
  
  // 1. dfs를 통해 4방향 탐색을 하면 'ㅜ'를 제외한 모든 모양을 만들 수 있다.
  public static void dfs(int x, int row, int col, int sum) {
    
    // 기저조건 : x == 4 이면 mySum과 sum의 값을 비교후 결과에 맞게 처리한 뒤 종료
    if(x >= 4) {
      mySum = Math.max(mySum, sum);
      return;
    }
    
    // 4방향 탐색을 시작한다.
    for(int i=0; i<4; ++i) {
      int ny = row + DELTAS[i][0];
      int nx = col + DELTAS[i][1];
      
      if( ny<0 || ny>=N || nx<0 || nx>=M || visited[ny][nx]) continue;
      
      visited[ny][nx] = true;
      dfs( (x+1), ny, nx, (sum+arr[ny][nx]) );
      visited[ny][nx] = false;
    } 
    
  } 
  
  
  // 2.'ㅜ'를 4방향 탐색을 해준다.
  // 중심을 기준으로 : 4방향 탐색을 모두했을 경우 그중 최솟값 하나를 빼주고 반환
  //                 : 3방향 탐색을 하였을 경우 바로 반환
  //                 : 그 밖에는 실패 했으므로 -1 반환
  static int getExceptCase(int row, int col) {
    
    int orginValue = arr[row][col];
    int minValue   = Integer.MAX_VALUE;
    int cnt        = 0; 
    
    // 중심을 기준으로 4방향 탐색
    for(int i=0; i<4; ++i) {
      int ny = row + DELTAS[i][0];
      int nx = col + DELTAS[i][1];
      
      if( ny<0 || ny>=N || nx<0 || nx>=M ) continue; 
      
      ++cnt;
      orginValue += arr[ny][nx];
      minValue = Math.min(minValue, arr[ny][nx]);
    }
    
    if(cnt == 4) return (orginValue - minValue);
    else if(cnt == 3) return orginValue;
    else return -1;
    
  }
 
  
  // main
  public static void main(String[] args) throws Exception{
    
    // Please Enter Your Code Here
    BufferedWriter bw  = new BufferedWriter(new OutputStreamWriter(System.out));
    BufferedReader br  = new BufferedReader(new InputStreamReader(System.in)); 
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
    
    visited = new boolean[N][M];
    arr     = new int[N][];
    for(int i=0; i<N; ++i) arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    
    // 모든위치에서 4방향 탐색을 통해 최대값을 구한다.
    for(int row=0; row<N; ++row) {
      for(int col=0; col<M; ++col) {
        
        visited[row][col] = true;
        // dfs를 통해 4방향 탐색을 하면 'ㅜ'를 제외한 모든 모양을 만들 수 있다.
        dfs(1, row, col, arr[row][col]);
        // 'ㅜ'를 4방향 탐색을 해준다.
        mySum = Math.max(mySum, getExceptCase(row, col));
        visited[row][col] = false;
        
      }
    }
    
    bw.write(String.valueOf(mySum));
    bw.flush();
    bw.close();
    br.close();
  } 
}