[백준] 14391 종이 조각 - 완전탐색(BruteForce) + DFS(깊이우선탐색) JAVA

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

14391번: 종이 조각

코드설명

완전탐색(BruteForce) + DFS(깊이우선탐색) 문제입니다.

 

문제에서 가장 중요한점은, 완전탐색을 통해서 각 종이조각을 가로로 나눌지, 세로로 나눌지 모두 정하는 것 입니다.

종이조각을 나누는 완전탐색 코드입니다.

• 사실 0으로 다시 초기화시켜주는 부분은 다음 함수 전에 이미 초기화되어서 상관없지만 추가해주었습니다.

public static void simulate(int level, int r, int c) {
    if(c >= M) {
        r = r + 1;
        c = 0;
    }
 
    if(r >= N) {
        caclulate();
 
        return ;
    }
 
    combination[r][c] = ROW;
    simulate(level + 1, r, c + 1);
    combination[r][c] = 0;
 
    combination[r][c] = COL;
    simulate(level + 1, r, c + 1);
    combination[r][c] = 0;
}

그리고 모든 종이조각을 나누었다면, 연산작업을 진행하면 됩니다.

 

visited[][] 로 가로, 세로 계산을 나누어서 진행해야하는 문제입니다.

만약 visited[i][j] = true 로 이루어져있다면, 해당 부분은 가로로 처리합니다.

만약 visited[i][j] = false 로 이루어져있다면, 해당 부분은 세로로 처리합니다.

헷갈리는 부분은, '행'을 기준으로 DFS 함수를 짯기떄문

 

DFS로써 종료조건을 잘 설정해야합니다.

종료조건은 행이 == N 이 되면 전체 계산을 종료한다는점

추가적인 조건 은 열이 >= M 이 되면 다음 열로 넘어가야한다는점 입니다. 또한 이미 col >= M 인 상태이기에 중지시켜줘야 col이 ArrayoutofIndex Exception이 나오지 않습니다.

 

전체 가로 계산을 하는 과정은 true, 즉 가로 일경우 연속적으로 더하기 처리해줍니다.

세로도 마찬가지입니다.

 

코드

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N,M, K;
	public static int[][] map;
	public static int[][] combination; //가로라면 TRUE, 세로라면 FALSE입니다.
	public static int ROW = 1, COL = 2;
	public static int answer = 0;
    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());
    	
    	map = new int[N][M];
    	combination = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String str = st.nextToken();
    		for(int j=0;j<M;j++) {
    			map[i][j] = str.charAt(j) - '0';
    		}
    	}
    	
    	simulate(0, 0, 0);
    	
    	System.out.println(answer);
    }
    
    public static void simulate(int level, int r, int c) {
    	if(c >= M) {
    		r = r + 1;
    		c = 0;
    	}
    	
    	if(r >= N) {
    		caclulate();
    		
    		return ;
    	}
    	
    	combination[r][c] = ROW;
    	simulate(level + 1, r, c + 1);
    	combination[r][c] = 0;
    	
    	combination[r][c] = COL;
    	simulate(level + 1, r, c + 1);
    	combination[r][c] = 0;
    }
    
    public static void caclulate() {
    	
    	boolean[][] visited = new boolean[N][M];
 
    	int wholeSum = 0;
    	//combination 배열을 돌면서 만약 가로일시 가능한 가로까지 모두 이동, 세로일시 가능한 세로까지 모두 이동합니다.
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(visited[i][j] == true) continue; //이미 방문한곳은 방문하지 않습니다.
    			
    			if(combination[i][j] == COL) {
    				int sum = map[i][j];
    				visited[i][j] = true;
    				int startCol = j + 1;
    				while(startCol < M && combination[i][startCol] == COL && visited[i][startCol] == false) {
    					sum = sum * 10 + map[i][startCol];
    					visited[i][startCol] = true;
    					startCol ++;
    				}
    				wholeSum += sum;
    			}
    			
    			
    			else if(combination[i][j] == ROW) {
    				int sum = map[i][j];
    				visited[i][j] = true;
    				int startRow = i + 1;
    				while(startRow < N && combination[startRow][j] == ROW && visited[startRow][j] == false) {
    					sum = sum * 10 + map[startRow][j];
    					visited[startRow][j] = true;
    					startRow ++;
    				}
    				wholeSum += sum;
    			}
    			
    		}
    	}
    	answer = Math.max(answer, wholeSum);
    }
    
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N,M;
	public static int[][] map; 
	public static boolean[][] visited; //방문처리
	public static int answer = Integer.MIN_VALUE;
    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());
    	map = new int[N][M];
    	visited = new boolean[N][M];
    	
    	for(int i=0;i<N;i++) {
    		String str = br.readLine();
    		for(int j=0;j<M;j++) {
    			map[i][j] = str.charAt(j) - '0';
    		}
    	}
    	
    	simulate(0, 0);
    	System.out.println(answer);
    	
    	
    	
    }
    
    public static void simulate(int row, int col) {
    	//행이 N과 같아지면, 탐색이 끝난것
    	if(row == N) {
    		calculate();
    		return ;
    	}
    	
    	//열 넘어가면 해당 로직처리
    	if(col >= M) {
    		simulate(row + 1, 0);
    		return ; //가로 계산이 끝나면 종료시켜야함.
    	}
    	
    	//가로라면 true처리
    	visited[row][col] = true;
    	simulate(row, col + 1);
    	
    	//가로 방문안한경우도 처리 ( 이경우 세로로 사용됨 )
    	visited[row][col] = false;
    	simulate(row, col + 1);
    	
    }
    
    public static void calculate() {
    	int result = 0;
    	int sumTemp = 0;
    	
    	//가로 계산
    	for(int i=0;i<N;i++) {
    		sumTemp = 0;
    		for(int j=0;j<M;j++) {
    			if(visited[i][j] == true) {
    				sumTemp *= 10;
    				sumTemp += map[i][j];
    			}else {
    				result += sumTemp;
    				sumTemp = 0;
    			}
    		}
    		//행 한줄 계산 끝날때마다 result에 + 연산 추가
    		result += sumTemp;
    	}
    	
    	for(int i=0;i<M;i++) {
    		sumTemp = 0;
    		for(int j=0;j<N;j++) {
    			if(visited[j][i] == false) {
    				sumTemp *= 10;
    				sumTemp += map[j][i];  
    			}else {
    				result += sumTemp;
    				sumTemp = 0;
    			}
    		}
    		result += sumTemp;
    	}
    	
    	answer = Math.max(answer,  result);
    	
    }
    
}