[문제풀이] 백준 14500 테트로미노

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

백준의 테트로미노 문제를 풀어보았습니다. 

DFS를 이용해서 푸는 문제였고, DFS로 처리하지 못하는 ㅗ,ㅏ,ㅜ,ㅓ 모양만 잘 처리하면 되는 문제였습니다.

import java.util.Scanner; import java.io.FileInputStream; public class Main { static int n,m; static int[][] arr; static int[][] visit; static int max_result; static int max; public static void main(String args[]) throws Exception{ Scanner scan=new Scanner(System.in); n=scan.nextInt(); m=scan.nextInt(); arr = new int[n][m]; visit = new int[n][m]; for(int i=0;i<n;i++) // N*M 크기의 배열에 값 입력받음 { for(int j=0;j<m;j++) { arr[i][j]=scan.nextInt(); } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++){ dfs(i,j,0); max=0; exception(i,j); max=0; } } System.out.println(max_result); scan.close(); return; } static void dfs(int x, int y, int cnt) { if(cnt == 4) // 4개 칸의 합을 세었으면 { if(max>=max_result){ //그 최대값이 지금까지 최대값보다 크면 max_result = max; // max_result 바꿈 return; } } visit[x][y]=1; max=max+arr[x][y]; cnt++; if(x>0 && visit[x-1][y]==0) // 위로이동 dfs(x-1,y,cnt); if(x<n-1 && visit[x+1][y]==0) //아래로 이동 dfs(x+1,y,cnt); if(y>0 && visit[x][y-1]==0) // 왼쪽으로 이동 dfs(x,y-1,cnt); if(y<m-1 && visit[x][y+1]==0) // 오른쪽으로 이동 dfs(x,y+1,cnt); visit[x][y]=0; max-=arr[x][y]; return; } static void exception(int i, int j){ //DFS로 처리 불가능한 예외 경우 처리 (ㅓ,ㅜ,ㅏ,ㅗ 모양) if(i-1>=0 && i+1<n && j-1>=0) { if(max_result < arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j-1]) max_result = arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j-1]; } if(i-1>=0 && i+1<n && j+1<m){ if(max_result < arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j+1]) max_result = arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j+1]; } if(i-1>=0 && j-1>=0 && j+1<m) { if(max_result < arr[i-1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]) max_result = arr[i-1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]; } if(i+1<n && j-1>=0 && j+1<m){ if(max_result < arr[i+1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]) max_result = arr[i+1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]; } } }

테스트케이스는 다 맞고, 에러도 안나는데 시간초과가 뜨네요..

조금 더 효율적인 방법으로 해보았습니다.

import java.util.Scanner; import java.io.FileInputStream; public class Main { static int N,M; static int[][] arr; static int[][] visit; static int MAX; static int sum; static int dx[]={1,-1,0,0}; static int dy[]={0,0,1,-1}; public static void main(String args[]) throws Exception{ //Scanner scan = new Scanner(new FileInputStream("test.txt")); Scanner scan = new Scanner(System.in); N=scan.nextInt(); M=scan.nextInt(); arr=new int[N][M]; visit=new int[N][M]; for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ arr[i][j]=scan.nextInt(); } } for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ DFS(i,j,0); sum=0; exception(i,j); sum=0; } } System.out.println(MAX); scan.close(); } static void DFS(int x, int y, int depth){ if(depth==4){ if(sum>MAX) MAX=sum; return; } visit[x][y]=1; sum+=arr[x][y]; for(int i=0; i<4; i++){ //이동할 수 있는 범위인지 확인하고 이동할 수 있는 범위이면 이동 int nx=x+dx[i]; int ny=y+dy[i]; if(nx>=0 && nx<N && ny>=0 && ny<M && visit[nx][ny]==0) DFS(nx,ny,depth+1); } visit[x][y]=0; sum-=arr[x][y]; } static void exception(int i, int j){ //DFS로 처리 불가능한 예외 경우 처리 (ㅓ,ㅜ,ㅏ,ㅗ 모양) if(i-1>=0 && i+1<N && j-1>=0) { if(MAX < arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j-1]) MAX = arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j-1]; } if(i-1>=0 && i+1<N && j+1<M){ if(MAX < arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j+1]) MAX = arr[i-1][j]+arr[i][j]+arr[i+1][j]+arr[i][j+1]; } if(i-1>=0 && j-1>=0 && j+1<M) { if(MAX < arr[i-1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]) MAX = arr[i-1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]; } if(i+1<N && j-1>=0 && j+1<M){ if(MAX < arr[i+1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]) MAX = arr[i+1][j]+arr[i][j]+arr[i][j-1]+arr[i][j+1]; } } }