[DFS] 백준 - 테트로미노

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

14500번: 테트로미노

 

-문제해설

이제부터 그래프가 나오면 웬만해서는 dfs, bfs풀이를 먼저 생각해야 겠다.

이 문제는 dfs를 이용하면 쉽게 풀 수 있는 문제이고 방문여부와 깊이를 잘 조정하면 각 도형에 대한 숫자 합을 구할 수 있다. 

 

먼저 dfs를 이용해서 아래 도형들을 구해준다.

그리고 ㅗ 도형에 대해서는 따로 구해주면 된다.

 

 

1. n, m 입력받고 그래프 저장할 arr, 방문여부배열 visit 선언

2. arr배열에 입력값 저장

3. 이중 포문을 돌면서 (0, 0)부터 각 도형에 따른 합을 구하기 위해 dfs 호출,

이때 함수 호출시에는 (0, 0)을 방문처리한다.

dfs메서드의 매개변수는 row = 행값, col = 열값, len = dfs깊이, sum = 현재깊이까지의 숫자 합

4. 상하좌우로 움직이기 위해 미리 선언한 dx, dy배열을 row와 col에 더해줘서 상하좌우에 해당되는 행렬에서 dfs를 재귀호출한다. 이때 해당 좌표는 방문처리하고 dfs함수 빠져나오면 다시 미방문으로 바꿔준다.

 

예를들어 (0, 0)에서 dfs를 호출하면 먼저 (0, 0)은 방문처리된다.

그리고 새로운 row와 col값을 만들어준다.

nrow = row + dy[0]

ncol = col + dx[0]

새로운 좌표값은 (0, 1)이되고 (0, 1)을 방문처리하고 (0, 1)의 dfs를 호출한다. dfs( nrow, ncol, len+1, sum+arr[row][col] )

(0, 1)에서 다시 nrow, ncol이 만들어지면 (0, 2)가 되고 또 dfs를 호출한다. dfs( nrow, ncol, len+1, sum+arr[row][col] )

(0, 2)에서 또 nrow, nocl만들고 dfs호출하면 (0, 3)이 되고 이때 len이 4이므로 ans값과 sum값을 비교해서 큰 값을 ans로 정의한다. ans = Math.max( ans, sum ); 여기까지오면 아래 모양에 대한 합이 만들어진 것이다. 

이제 return돼서 (0,2)로 돌아오고 (0,3)은 다시 미방문처리로 만든다. 나중에 다른 모형에서 다시 방문해야되기 때문이다.

 

이제 다시 (0,2)로 돌아와서 다음 nrow, ncol값인 (1, 2 )에서 dfs를 호출한다. 이렇게 되면 ( 1, 2 )에서 len은 4이므로 ans와 sum을 비교해서 큰 값으로 ans를 초기화시켜준다. 이렇게 되면 아래 모양의 합이 만들어진 것이다.

이제 return으로 (0,1)로 돌아오고 (0,2)는 다시 미방문 처리로 만든다.

 

이제 (0,1)에서 우측방향인 (1,1)에서 dfs를 호출한다. (1,1)에서 갈 수 있는 방향은 하, 상, 우측 뿐이다.

먼저 아래쪽으로 가면 (2,1)을 방문처리하고 dfs를 호출한다. 

(2, 1)로 이동하면 len은 4가 돼서 ans와 여태까지의 sum합과 비교해서 ans는 더 큰 값으로 치환된다.

그러면 아래와 같은 모형의 합을 구하게 된 것이다.

이렇게 (0,0)에서 4칸 이내로 만들어질 수 있는 모든 도형은 만들어진다. 아래는 (0,0)에서 갈 수 있는 모든 좌표를 나타낸 것이다.

ㅇ	ㅇ	ㅇ	ㅇ
ㅇ	ㅇ	ㅇ
ㅇ	ㅇ
ㅇ

이런식으로 (0,0)에서 (4,4)까지 모두 구하면 된다.

 

5. 이제 아래 도형은 따로 구해주면 된다.

이 모형을 구하는 방법은 메소드를 추가로 만들고 ㅗ ㅜ ㅏ ㅓ 를 일일이 구해주면 된다.

만약 (0, 1)에서 ㅗ ㅜ ㅏ ㅓ를 구한다고 할 경우 

 

먼저 ㅗ를 구할 때

row-1 이 0 이상이고 col-1은 0이상이고 col+1은 m 미만일 경우

sum = arr[row][col-1] + arr[row][col] + arr[row][col+1] + arr[row-1][col] 을 해주면 되는데

현재 row값이 0 이고 row-1은 -1이 되므로 (0, 1)에서 ㅗ는 구하지 못한다.

 

ㅜ를 구하면

row+1 이 n 미만이고 col-1은 0이상이고 col+1은 m 미만일 경우

sum = arr[row][col-1] + arr[row][col] + arr[row][col+1] + arr[row+1][col] 을 해주면 된다.

 

이런식으로 ㅏ, ㅓ도 구하면 된다.

 

자세한 내용은 코드 참조...

 

 

 

-자바

package bruteforce;

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

public class BJ14500 {
	static int n, m, ans;
	static int[][] arr, visit;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	
	public static void dfs( int row, int col, int len, int sum ) {
		if( len == 4 ) {
			ans = Math.max( ans, sum );
			return;
		}
		
		for( int i=0; i<4; i++ ) {
			int nrow = row + dy[i];
			int ncol = col + dx[i];
			
			if( nrow<0 || ncol<0 || nrow>=n || ncol>=m ) continue;
			if( visit[nrow][ncol] == 1 ) continue;
			
			visit[nrow][ncol] = 1;
			dfs( nrow, ncol, len+1, sum+arr[nrow][ncol] );
			visit[nrow][ncol] = 0;
		}
	}
	
	public static void additionalPlus( int row, int col ) {
		int sum = 0;
		
		//ㅗ ㅜ ㅏ ㅓ 순으로 비교
		//ㅗ
		if( row-1>=0 && col-1>=0 && col+1<m ) {
			sum = arr[row-1][col] + arr[row][col-1] + arr[row][col] + arr[row][col+1];
			ans = Math.max( ans, sum );
			sum = 0;
		}
		
		//ㅜ
		if( row+1<n && col-1>=0 && col+1<m ) {
			sum = arr[row+1][col] + arr[row][col-1] + arr[row][col] + arr[row][col+1];
			ans = Math.max( ans, sum );
			sum = 0;
		}
		
		//ㅏ
		if( row-1>=0 && row+1<n && col+1<m ) {
			sum = arr[row-1][col] + arr[row][col] + arr[row][col+1] + arr[row+1][col];
			ans = Math.max( ans, sum );
			sum = 0;
		}
		
		//ㅓ
		if( row-1>=0 && row+1<n && col-1>=0 ) {
			sum = arr[row-1][col] + arr[row][col] + arr[row][col-1] + arr[row+1][col];
			ans = Math.max( ans, sum );
			sum = 0;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer( br.readLine() );
		n = Integer.parseInt( st.nextToken() );
		m = Integer.parseInt( st.nextToken() );
		
		arr = new int[n][m];
		visit = new int[n][m];
		for( int i=0; i<n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( int j=0; j<m; j++ ) {
				arr[i][j] = Integer.parseInt( st.nextToken() );
			}
		}
		
		for( int i=0; i<n; i++ ) {
			for( int j=0; j<m; j++ ) {
				visit[i][j] = 1;
				dfs( i, j, 0, 0 );
				visit[i][j] = 0;
				additionalPlus( i, j );
			}
		}
		System.out.println( ans );
		
	}
}

 

-파이썬(pypy3로 해야지 통과)

from sys import stdin
input = stdin.readline

def dfs( row, col, length, hap, arr, drow, dcol ):
    global ans
    global n
    global m
    if length == 4:
        ans = max( [ ans, hap ] )
        return
    
    for i in range( 4 ):
        nrow = row + drow[i]
        ncol = col + dcol[i]
        
        if nrow<0 or ncol<0 or nrow>=n or ncol>=m: continue
        if visit[nrow][ncol] == 1: continue
        
        visit[nrow][ncol] = 1
        dfs( nrow, ncol, length+1, hap+arr[row][col], arr, drow, dcol )
        visit[nrow][ncol] = 0

def additionalPlus( row, col, arr, n, m ):
    global ans
    #ㅗ
    hap = 0
    if row-1>=0 and col-1>=0 and col+1<m:
        hap = arr[row][col-1] + arr[row][col] + arr[row][col+1] + arr[row-1][col]
        ans = max( [hap, ans] )
    
    #ㅜ
    hap = 0
    if row+1<n and col-1>=0 and col+1<m:
        hap = arr[row][col-1] + arr[row][col] + arr[row][col+1] + arr[row+1][col]
        ans = max( [hap, ans] )
    
    #ㅏ
    hap = 0
    if row-1>=0 and row+1<n and col+1<m:
        hap = arr[row-1][col] + arr[row][col] + arr[row+1][col] + arr[row][col+1]
        ans = max( [hap, ans] )
    
    #ㅓ
    hap = 0
    if row-1>=0 and row+1<n and col-1<m:
        hap = arr[row-1][col] + arr[row][col] + arr[row+1][col] + arr[row][col-1]
        ans = max( [hap, ans] )
        
if __name__ == "__main__":
    n, m = map(int, input().split())
    drow = [ 1, -1, 0, 0 ]
    dcol = [ 0, 0, 1, -1 ]
    ans = 0
    arr = []
    visit = [ [0]*m for _ in range( n ) ]
    for i in range( n ):
        arr.append( list( map(int, input().split()) ) )
    
    for i in range( n ):
        for j in range( m ):
            visit[i][j] = 1
            dfs( i, j, 0, 0, arr, drow, dcol )
            visit[i][j] = 0
            
            additionalPlus( i, j, arr, n, m )
            
    print( ans )