티스토리 뷰

Study/알고리즘 문제풀이

백준 14500. 테트로미노 :: 돼지개발자

돼지개발자 2019. 1. 17. 01:02

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


"DFS 로 4칸을 간다. ㅗ 경우는 별도로 처리"


DFS를 통해 4칸을 이동하면 테트로미노의 도형 4가지를 구할 수 있다. 문제는 <ㅗ> 의 처리이다. 아래와 같이 처리해 주었다.


map을 다시 for 문을 돌면서 4개 셀의 값을 선택하여 처리한다. 

1 : ㅗ 만들 수 없는 경우
2 : 그냥 선택한 4개 셀을 다 더하면 되는 경우
3 : 중앙값 + ( 4개 셀의 값 - 이중 최소인 값)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main {
 
    static int n,m;
    static int map[][];
    static boolean visited[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    static int max = 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];
        visited = new boolean[n][m];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = true;
                solve(i,j,1,map[i][j]);
                visited[i][j] = false;
            }
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int min = Integer.MAX_VALUE;
                int sum = map[i][j];
                int cell = 0;
                
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(!isRange(nx, ny)) {
                        cell++;
                        continue;
                    }
                    min = Math.min(min, map[nx][ny]);
                    sum += map[nx][ny];
                }
                if(cell >= 2) {
                    continue;
                }
                else if ( cell == 1) {
                    max = Math.max(max, sum);
                }
                else {
                    max = Math.max(max, sum - min);    
                }
            }
        }
        System.out.println(max);
    }
    
    static void solve(int x, int y, int cnt, int sum) {
        if(cnt == 4) {
            max = Math.max(max, sum);
            return;
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = x +dx[i];
            int ny = y +dy[i];
            
            if( !isRange(nx, ny) || visited[nx][ny])
                continue;
            
            visited[nx][ny] = true;
            solve(nx, ny, cnt+1, sum + map[nx][ny]);
            visited[nx][ny] = false;
        }
    }
    
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= n || y < 0 || y >= m) return false;
        return true;
    }
}
cs



저작자표시

'Study > 알고리즘 문제풀이' 카테고리의 다른 글

백준 14890. 경사로 :: 돼지개발자  (0) 2019.01.19
백준 15686. 치킨 배달 :: 돼지개발자  (0) 2019.01.17
백준 14501. 퇴사 :: 돼지개발자  (0) 2019.01.16
백준 2309. 일곱난쟁이 :: 돼지개발자  (1) 2019.01.16
백준 9205. 맥주 마시면서 걸어가기 :: 돼지개발자  (0) 2019.01.16
댓글
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday