[Java]백준 BaekJoon.AC 14500 : 테트로미노 (dfs, 노가다 사용)

 

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

14500번: 테트로미노

 

 

 

 

와! 내가 생각해도 효율성 꽝인 코드다ㅋㅋㅋ

사실 효율성이라기보다 코드가 참 길다..

코딩하면서도 '하... 이게 아닐텐데...' 무한반복하며 끝끝내 완성했다!^^

내 우물파기 실력과 인내심과 자존감에 박수를 보낸다.

(훌륭한 성적으로) 채점을 통과했음을 인지하곤 그냥 뿌듯하기만 하더라;;ㅋㅋ

 

 

「이 문제의 핵심은 브루트포스 알고리즘을 이용해 모든 경우를 다 조사하는 것이다.

그러기 위해선 모든 칸을 돌며 그 칸마다 그릴 수 있는 블럭을 모든 방향으로 돌려가며 구해봐야 한다.

ㅏ 모양을 제외한 모든 블럭은 출발점에서 임의의 도착점까지 모든 칸을 훑으며 단번에 이동할 수 있다. 쉽게 bfs가 가능하단 얘기다.

하지만 ㅏ 모양은 쉽게 말해 갈림길이 존재하기 때문에 앞선 블럭과 다른 관심이 필요하다.

이 점만 염두하고 차근히 이해한다면 해결할 수 있는 문제였다.」

 

 

그래도 조금 부끄러워서 이걸 올려야 하나 싶었지만..

다른 사람들이 한 코드를 보고 귀찮아서 쿨하게 포기했다..

 

내 근본없는 자신감은 분명 나처럼 한 사람이 있을 거라고, 그 사람은 내 도움이 필요할지 모른다고 응원해주고 있다...!

생각해보니 내 코드가 (근-본)인 코드인 것 같기도 하고ㅎ

for문과 if문을 마구 남발해 만든 코드가 초보자가 전형적으로 작성하는, 바로 근본을 추구하는 코드 아니겠는가?

 

글을 적다보니 자신감이 더 생긴다;;ㅋ

나중에 더 나은 코드로 수정할 생각으로 원초적인 코드를 여기 남긴다.

 

다시 말하자면 이 코드는 훌륭히 채점을 통과한 코드다!

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int maxR = 0;
	static int[][] score;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	score = new int[N][M];
    	
    	for(int i=0; i<N; i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int k=0; k<M; k++) {
    			score[i][k] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	for(int i=0; i<N; i++) {
    		for(int k=0; k<M; k++) {
    			
    			if(i!=0) {
    				up(i, k, 1, score[i][k]);
    			}
    			if(i!=N-1) {
    				down(i, k, 1, score[i][k]);
    			}
    			if(k!=0) {
    				left(i, k, 1, score[i][k]);
    			}
    			if(k!=M-1) {
    				right(i, k, 1, score[i][k]);
    			}
    			
    			  exception(i, k);
    		}
    	}
    	
    	System.out.print(maxR);
	
	}
	
	public static void up(int col, int row, int count, int sum) {
		
		if(count==4) {
			if(sum>maxR) {
				maxR = sum;
			}
			return;
		}
		
		if(col!=0) {
			up(col-1, row, count+1, sum+score[col-1][row]);
		}
		if(row!=0) {
			left(col, row-1, count+1, sum+score[col][row-1]);
		}
		if(row!=M-1) {
			right(col, row+1, count+1, sum+score[col][row+1]);
		}
		
	}
	
	public static void down(int col, int row, int count, int sum) {
		
		if(count==4) {
			if(sum>maxR) {
				maxR = sum;
			}
			return;
		}
		
		if(col!=N-1) {
			down(col+1, row, count+1, sum+score[col+1][row]);
		}
		if(row!=0) {
			left(col, row-1, count+1, sum+score[col][row-1]);
		}
		if(row!=M-1) {
			right(col, row+1, count+1, sum+score[col][row+1]);
		}
	}
	
	public static void left(int col, int row, int count, int sum) {
		
		if(count==4) {
			if(sum>maxR) {
				maxR = sum;
			}
			return;
		}
		
		if(col!=0) {
			up(col-1, row, count+1, sum+score[col-1][row]);
		}
		if(col!=N-1) {
			down(col+1, row, count+1, sum+score[col+1][row]);
		}
		if(row!=0) {
			left(col, row-1, count+1, sum+score[col][row-1]);
		}
		
	}
	
	public static void right(int col, int row, int count, int sum) {
		
		if(count==4) {
			if(sum>maxR) {
				maxR = sum;
			}
			return;
		}
		
		if(col!=0) {
			up(col-1, row, count+1, sum+score[col-1][row]);
		}
		if(col!=N-1) {
			down(col+1, row, count+1, sum+score[col+1][row]);
		}
		if(row!=M-1) {
			right(col, row+1, count+1, sum+score[col][row+1]);
		}
	}
	
	public static void exception(int x, int y) {
		
		int sum = 0;
	  
	    if(x>=0 && x<=N-2 && y>=1 && y<=M-2){
	        sum = score[x][y] + score[x+1][y] + score[x][y-1] + score[x][y+1];
	        if(sum>maxR) {
				maxR = sum;
			}
	    }

	    if(x>=1 && x<=N-2 && y>=0 && y<=M-2){
	        sum = score[x][y] + score[x-1][y] + score[x+1][y] + score[x][y+1];
	        if(sum>maxR) {
				maxR = sum;
			}
	    }
	
	    if(x>=1 && x<=N-1 && y>=1 && y<=M-2){
	        sum = score[x][y] + score[x][y-1] + score[x][y+1] + score[x-1][y];
	        if(sum>maxR) {
				maxR = sum;
			}
	    }

	    if(x>=1 && x<=N-2 && y>=1 && y<=M-1){
	        sum = score[x][y] + score[x-1][y] + score[x+1][y] + score[x][y-1];
	        if(sum>maxR) {
				maxR = sum;
			}
	    }
	}
}