# 유형 : 시뮬레이션

# 난이도 : 골드 V

# 배열이나 리스트 처리만 잘 생각하고 계절에 맞게 구현만 해준다면 어렵지 않은 시뮬레이션 문제였다.

 

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class p16235 {
    static int N,M,K;
    static int arr[][], map[][];
    static int moveX[] = {0,1,1,1,0,-1,-1,-1};
    static int moveY[] = {-1,-1,0,1,1,1,0,-1};
    static ArrayList<Integer> arrList[][];
    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());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][N+1];
        map = new int[N+1][N+1];
        
        arrList = new ArrayList[N+1][N+1];
        for(int i=1; i<=N; i++)
            for(int j=1; j<=N; j++)
                arrList[i][j] = new ArrayList<>();
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++)
                map[i][j] = 5;
        }
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) 
                arr[i][j] = Integer.parseInt(st.nextToken());
                
        }
        for(int m=1; m<=M; m++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int age = Integer.parseInt(st.nextToken());
            arrList[u][v].add(age);
        }
        int k = 0;
        while(k<K) {
            
            // 봄 + 여름
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(arrList[i][j].size() > 0) {
                        int end = 0;
                        Collections.sort(arrList[i][j]);
                        
                        ArrayList<Integer> tmp = new ArrayList<>();
                        for(int q=0; q<arrList[i][j].size(); q++) {
                            int age = arrList[i][j].get(q);
                            if(map[i][j] >= age) {
                                map[i][j] -= age;
                                tmp.add(age+1);
                            }else {
                                end += age/2;
                            }
                        }
                        arrList[i][j] = new ArrayList<>();
                        for(int val : tmp)
                            arrList[i][j].add(val);
                        
                        map[i][j] += end;
                    }
                }
            }
            
            /// 가을
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(arrList[i][j].size() > 0) {
                        
                        for(int q=0; q<arrList[i][j].size(); q++) {
                            int age = arrList[i][j].get(q);
                            if(age % 5 == 0) {
                                for(int d=0; d<8; d++) {
                                    int newX = j + moveX[d];
                                    int newY = i + moveY[d];
                                    if(0<newX && newX<=N && 0<newY && newY<=N) {
                                        arrList[newY][newX].add(1);
                                    }
                                }
                            }
                        }
                    }
                }
            }
            
            /// 겨울
            for(int i=1; i<=N; i++)
                for(int j=1; j<=N; j++)
                    map[i][j] += arr[i][j];
            
            
            k++;
        }
        int result = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                result += arrList[i][j].size();
            }
        }
        System.out.println(result);
    }
}
    
 
 cs

'백준' 카테고리의 다른 글

#백준_14890 경사로 - Java 자바  (0) 2020.03.25
#백준_13458 시험 감독 - Java 자바  (0) 2020.03.25
#백준_17136 색종이 붙이기 - Java 자바  (0) 2020.03.23
#백준_17135 캐슬 디펜스 - Java 자바  (0) 2020.03.21
#백준_17406 배열 돌리기 4 - Java 자바  (0) 2020.03.20

# 유형 : DFS, 브루트포스

# 난이도 : 골드 3

# 설명은 주석으로 달아놨습니다 : )

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p17136 {
    // 각 크기별 색종이 개수
    static int map[] = {0, 5, 5, 5, 5, 5};
    static int arr[][];
    static int result=0, minValue = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new int[10][10];
        StringTokenizer st;
        for(int i=0; i<10; i++) {
             st = new StringTokenizer(br.readLine());
             for(int j=0; j<10; j++)
                 arr[i][j] = Integer.parseInt(st.nextToken());
        }
        dfs(0,0);
        // 1로 모두 덮는 것이 불가능할 때
        if(minValue == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(minValue);
    }
    
    public static void dfs(int currentX, int currentY) {
        // 세로 한칸에 해당하는 가로 탐색이 끝났을때 y 인덱스 + 1
        if(currentX == 10) {
            dfs(0, currentY+1);
            return;
        }
        // y 인덱스가 10 이면 탐색이 끝난 것 => currentX=9, currentY=9에서 currentX=10, currentY=9 -> currnetX=0 , currentY=10 호출
        if(currentY == 10) {
            minValue = Math.min(minValue, result);
            return;
        }
        // 0이면 해당 부분은 그냥 넘어간다.
        if(arr[currentY][currentX] == 0) {
            dfs(currentX+1, currentY);
            return;
        }
        
        // arr[currentY][currentX] == 1 이면 해당하는 부분부터 사이즈에 맞는 색종이를 붙여본다.
        for(int size=5; size>0; size--) {
            boolean isPossible = true;
            
            if(map[size] == 0 || currentY + size > 10 || currentX + size > 10) 
                continue;
            
            for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) {
                    if(arr[currentY + i][currentX + j] == 0) {
                        isPossible = false;
                        break;
                    }
                }
                if(!isPossible)
                    break;
            }
            // 해당 사이즈가 불가능하면 Continue
            if(!isPossible)
                continue;
            
            // 해당 사이즈가 가능하면 0 으로 채워준다.
            for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) {
                    arr[currentY + i][currentX + j] = 0; 
                }
            }
            // 해당 사이즈의 색종이 개수 -1, 사용한 개수 +1
            map[size]--;
            result++;
            
            dfs(currentX + size, currentY);
            
            // 백트래킹을 위해 복구
            for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) {
                    arr[currentY + i][currentX + j] = 1; 
                }
            }
            
            map[size]++;
            result--;
        }
            
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_13458 시험 감독 - Java 자바  (0) 2020.03.25
#백준_16235 나무 재테크 - Java 자바  (0) 2020.03.24
#백준_17135 캐슬 디펜스 - Java 자바  (0) 2020.03.21
#백준_17406 배열 돌리기 4 - Java 자바  (0) 2020.03.20
#백준_17070 파이프 옮기기1 - Java 자바  (0) 2020.03.19

# 유형 : 조합 using DFS + 시뮬레이션

# 난이도 : 골드 4

# 조합을 통해 궁수의 위치를 정한다. 정한 후, 조건에 맞게 사격, 남은 적들은 y칸들을 1씩 증가. 이 작업을 적이 다 죽거나 궁수 있는 곳까지 도달할 때까지 반복한다.

 

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p17135 {
    
    static int N,M,D, maxValue = Integer.MIN_VALUE;
    static int arr[][], cpArr[][], tmp[], ar[];
    static ArrayList<Point> enemy, set;
    
    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());
        D = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][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());
            }
        }
        
        tmp = new int[M];
        ar = new int[3];
        for(int i=0; i<tmp.length; i++)
            tmp[i] = i;
        
        combination(0, 0);
        System.out.println(maxValue);
    }
    
    public static void combination(int len, int k) {
        
        if(len == 3) {
            enemy = new ArrayList<>();
            set = new ArrayList<>();
            cpArr = new int[N+1][M];
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    cpArr[i][j] = arr[i][j];
                    if(arr[i][j]==1)
                        enemy.add(new Point(j,i));
                }
            }
                
            
            for(int i=0; i<3; i++) {
                cpArr[N][tmp[ar[i]]] = -1;
                set.add(new Point(ar[i], N));
            }
            
            solve(cpArr);
            return;
        }
        
        if(k == M)
            return;
        
        ar[len] = tmp[k];
 
        combination(len+1, k+1);
        combination(len, k+1);
    }
    
    public static int getDist(Point p1, Point p2) {
        return Math.abs(p1.x-p2.x)+Math.abs(p1.y-p2.y);
    }
 
    private static void solve(int[][] cpArr2) {
        // TODO Auto-generated method stub
        int result = 0;
        
        // 모든 적이 격자판에서 제외되면 게임이 끝난다. 
        while(!enemy.isEmpty()) {
            ArrayList<Point> remove = new ArrayList<>();
            for(int i=0; i<set.size(); i++) {
                int dir[] = new int[enemy.size()];
                int min = Integer.MAX_VALUE;
                
                //가장 가까운 적을 찾자
                for(int j=0; j<enemy.size(); j++) {
                    dir[j] = getDist(set.get(i), enemy.get(j));
                    min = Math.min(min, dir[j]);
                }
                
                ArrayList<Point> Possible = new ArrayList<>();
                for(int j=0; j<enemy.size(); j++) {
                    if(dir[j] == min && dir[j] <= D) {
                        Possible.add(enemy.get(j));
                    }
                }
                
                if(Possible.size() == 0) {
                    continue;
                }
                else if(Possible.size() == 1) {
                    remove.add(Possible.get(0));
                }
                // 2개 이상인 경우에는 가장 왼쪽
                else {
                    int minCol = 100;
                    for(int j=0; j<Possible.size(); j++) {
                        minCol = Math.min(minCol, Possible.get(j).x);
                    }
                    for(int j=0; j<Possible.size(); j++) {
                        if(Possible.get(j).x == minCol)
                            remove.add(Possible.get(j));
                    }
                    
                }
            }
            
            for(int i=0; i<remove.size(); i++){
                for(int j=0; j<enemy.size(); j++) {
                    if(remove.get(i).y == enemy.get(j).y && remove.get(i).x == enemy.get(j).x) {
                        enemy.remove(j);
                        result++;
                        break;
                    }
                }
            }
            
            int size = enemy.size();
            while(size>0) {
                if(enemy.get(0).y + 1 != N)
                    enemy.add(new Point(enemy.get(0).x, enemy.get(0).y+1));
                enemy.remove(0);
                size--;
            }
        }
        maxValue = Math.max(maxValue, result);
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_16235 나무 재테크 - Java 자바  (0) 2020.03.24
#백준_17136 색종이 붙이기 - Java 자바  (0) 2020.03.23
#백준_17406 배열 돌리기 4 - Java 자바  (0) 2020.03.20
#백준_17070 파이프 옮기기1 - Java 자바  (0) 2020.03.19
#백준_16637 괄호 추가하기  (0) 2020.03.18

# 유형 : 그래프 탐색 + 시뮬레이션

# 난이도 : 골드 V

# 시뮬레이션 문제는 항상 설명이 길어서 어렵다. 문제를 제대로 이해 안 하고 풀어서 회전할 때마다 minValue 값을 구하게 했는데, 알고 보니 회전을 다 돌리고 나서의 minValue 값을 구하는 거였다. 순서를 어떻게 적용할지는 DFS를 통해 정하였고 나머진 그대로 구현하였다. 코드에 주석을 달아놓았으니 참고하면 좋을듯하다

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p17406 {
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static ArrayList<Integer> arrList = new ArrayList<>();
    static int N,M,K;
    static int arr[][], tmp[][];
    static boolean visit[];
    static Po poArr[];
    static int minValue = Integer.MAX_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());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N+1][M+1];
        tmp = new int[N+1][M+1];
        visit = new boolean[K+1];
        poArr = new Po[K+1];
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                tmp[i][j] = arr[i][j];
            }
        }
        for(int k=1; k<=K; k++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            poArr[k] = new Po(r,c,s);
        }
        
        dfs();
        System.out.println(minValue);
    }
    
    public static void dfs() {
        if(arrList.size() == K) {
            
            for(int i=1; i<=N; i++) 
                arr[i] = tmp[i].clone();
            
            for(int i=0; i<arrList.size(); i++) 
                solve(arrList.get(i));
 
            for(int j=1; j<=N; j++) {
                int sum = 0;
                for(int k=1; k<=M; k++) {
                    sum += arr[j][k];
                }
                minValue = Math.min(minValue, sum);
            }
            return;
        }
        
        //전형적인 DFS 탐색 기법
        for(int i=1; i<=K; i++) {
            if(!visit[i]) {
                visit[i] = true;
                arrList.add(i);
                dfs();
                arrList.remove(arrList.size()-1);
                visit[i] = false;
            }
        }
    }
 
    public static void solve(int index) {
        int startX = poArr[index].c - poArr[index].s;
        int startY = poArr[index].r - poArr[index].s;
        int endX = poArr[index].c + poArr[index].s;
        int endY = poArr[index].r + poArr[index].s;
        
        int currentX = startX;
        int currentY = startY;
        
        int dir = 1; // 회전하는 순서가 동->남->서->북 (위에 이동하는 배열에는 북->동->남->서로 했기에 1값을 주었다)
        
        int currentVal = arr[currentY][currentX];
        int newX = currentX;
        int newY = currentY;
        
        while(true) {
            
            newX += moveX[dir];
            newY += moveY[dir];
            
            if(newX >= startX && newX <= endX && newY >= startY && newY <= endY) {
                int temp = arr[newY][newX];
                arr[newY][newX] = currentVal;
                currentVal = temp;
                currentX = newX;
                currentY = newY;
            }else {
                newX = currentX;
                newY = currentY;
                dir++;
                dir%=4;
            }
            
            //만약 일치한다면 회전을 다한 경우이다. 따라서 시작점들은 +1 씩 해주고, 끝점들은 -1씩 해준다. 그리고 현재 인덱스와 현재 값,현재 방향을 수정해준다.
            if(currentX == startX && currentY == startY) {
                startX += 1;
                startY += 1;
                endX -= 1;
                endY -= 1;
                currentX = startX;
                currentY = startY;
                newX = currentX;
                newY = currentY;
                dir = 1;
                currentVal = arr[currentY][currentX];
            }
            
            //시작점과 끝점이 늘어나고 줄어들다가 겹칠때 또는 차이가 1날때 종료해준다.
            if((startX==endX && startY==endY) || (endX-startX==1 && endY-startY==1))
                break;
        }
    }
    
    //회전 연산 저장을 위한 클래스
    public static class Po{
        int r;
        int c;
        int s;
        public Po(int r, int c, int s) {
            this.r=r;
            this.c=c;
            this.s=s;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_17136 색종이 붙이기 - Java 자바  (0) 2020.03.23
#백준_17135 캐슬 디펜스 - Java 자바  (0) 2020.03.21
#백준_17070 파이프 옮기기1 - Java 자바  (0) 2020.03.19
#백준_16637 괄호 추가하기  (0) 2020.03.18
#백준_17471 게리맨더링 - Java 자바  (0) 2020.03.17

# 유형 : 브루트 포스, 그래프 탐색

# 난이도 : 골드 V

# 브루트 포스 문제인데, BFS로 접근해서 해결하려다 테스트케이스와 같이 답은 나오지만 시간초과가 났다. 그래서 검색을 해봤더니

***BFS는 같은 정점을 한 번 방문해야 하는데, 같은 정점을 여러 번 방문하는 BFS와 같은 소스가 많습니다.

이건 브루트 포스를 Queue를 이용해서 BFS처럼 구현한 것입니다.*** 라고 하였다. 따라서 그냥 재귀함수로 해결하였다.

 

팁

1. 가로로 놓여져있는 경우 세로로 못간다. <-> 세로도 가로로 못간다.

2. 범위를 벗어나거나 벽이면 못간다.

3. 대각선으로 이동시에 오른쪽 또는 아래가 막혀있으면 못간다.

 

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
94
95
96
97
98
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p17070 {
    static int N, result = 0;
    static int arr[][];
    static int moveX[] = {1,0,1};
    static int moveY[] = {0,1,1};
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
//        bfs();
        solve(2,1,0);
        System.out.println(result);
    }
    
    private static void solve(int x, int y, int what) {
        // TODO Auto-generated method stub
        if(x == N && y == N) {
            result++;
            return;
        }
        for(int d=0; d<3; d++) {
            
            int newY = y + moveY[d];
            int newX = x + moveX[d];
            
            // 가로인 상황에서 세로로 이동 불가능 <->세로에서 가로도 불가능
            if((d==1 && what==0) || (d==0 && what==1))
                continue;
            
            // 범위를 벗어나거나 벽일때
            if(newY > N || newX > N || arr[newY][newX] ==1)
                continue;
            
            // 대각선인데 오른쪽 또는 아래가 벽이 있는 경
            if(d==2 && (arr[y][x+1]==1 || arr[y+1][x] ==1))
                continue;
            
            solve(newX,newY,d);
        }
    }
 
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Po> queue = new LinkedList<>();
        queue.add(new Po(2,1,0));
        
        while(!queue.isEmpty()) {
            Po p = queue.poll();
            if(p.x == N && p.y == N) {
                result++;
                continue;
            }
            
            for(int d=0; d<3; d++) {
                
                int newX = p.x + moveX[d];
                int newY = p.y + moveY[d];
                
                if((d==1 && p.what==0) || (d==0 && p.what==1))
                    continue;
                
                if(newY > N || newX > N || arr[newY][newX] ==1)
                    continue;
                
                if(d==2 && (arr[p.y][p.x+1]==1 || arr[p.y+1][p.x] ==1))
                    continue;
                
                queue.add(new Po(newX, newY, d));
            }
        }
    }
    public static class Po{
        int x;
        int y;
        int what;
        public Po(int x, int y, int what) {
            this.x=x;
            this.y=y;
            this.what=what;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_17135 캐슬 디펜스 - Java 자바  (0) 2020.03.21
#백준_17406 배열 돌리기 4 - Java 자바  (0) 2020.03.20
#백준_16637 괄호 추가하기  (0) 2020.03.18
#백준_17471 게리맨더링 - Java 자바  (0) 2020.03.17
#백준_17281 ⚾ - Java 자바  (0) 2020.03.16

# 유형 : 그래프 탐색, DFS

# 난이도 : 골드 3

# 설명은 주석을 통해 남겨두었음.

 

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p16637 {
    static int N, maxValue = Integer.MIN_VALUE;
    static char arr[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new char[N];
        String str = br.readLine();
        arr = str.toCharArray();
        dfs(1,arr[0]-'0',0, false);
        System.out.println(maxValue);
    }
    
    // 괄호쳐서 계산하기 위한 previous값, 연속해서 괄호를 칠수 없으므로 이것을 체크하기 위한 imPossible, 
    private static void dfs(int index, int current, int previous, boolean imPossible) {
        // TODO Auto-generated method stub
        
        //마지막 인덱스 일때 Max값 비교
        if(index >= N) {
            maxValue = Math.max(maxValue, current);
            return;
        }
        
        // 괄호를 치지 않는다면 현재까지의 값을 계산해야하므로 next 변수에 저장, index+2인 이유는 인덱스는 2를 간격으로 배열에 저장되어있다.
        int next = cal(current, arr[index+1]-'0', arr[index]);
        dfs(index+2, next, current, false);
        
        //연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 따라서 인덱스가 1일 경우에 괄호치는 것은 의미가 없다.
        // 괄호를 칠 때
        if(index>1 && !imPossible) {
            next = cal(arr[index-1]-'0',arr[index+1]-'0',arr[index]);
            dfs(index+2, cal(previous, next, arr[index-2]), 0, true);
        }
    }
 
    static int cal(int a, int b, char ch) {
        if(ch == '+')
            return a+b;
        else if(ch == '-')
            return a-b;
        else
            return a*b;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_17406 배열 돌리기 4 - Java 자바  (0) 2020.03.20
#백준_17070 파이프 옮기기1 - Java 자바  (0) 2020.03.19
#백준_17471 게리맨더링 - Java 자바  (0) 2020.03.17
#백준_17281 ⚾ - Java 자바  (0) 2020.03.16
#백준_1986 체스 - Java 자바  (1) 2020.03.12

# 유형 : 그래프 탐색, DFS

# 난이도 : 골드 V

# 맨날 BFS 풀다가 DFS로 접근하려니까 어렵다. DFS탐색을 통해 선거구를 1,2 로 나눈다. 만약 선거구가 3개이상이라면 선거구 지역이 끊겨있는 것이다. 

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p17471 {
    static int N, minValue = 99999999;
    static int arr[],connect[][],area[];
    static boolean visit[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N+1];
        for(int i=1; i<=N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        
        connect = new int[N+1][N+1];
        area = new int[N+1];
        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            int iter = Integer.parseInt(st.nextToken());
            for(int j=1; j<=iter; j++) {
                int val = Integer.parseInt(st.nextToken());
                connect[i][val] = 1;
                connect[val][i] = 1;
            }
        }
        dfs(1);
        if(minValue == 99999999)
            System.out.println(-1);
        else
            System.out.println(minValue);
        
    }
    private static void dfs(int count) {
        // TODO Auto-generated method stub
        if(count == N+1) {
            int area1 = 0, area2 = 0;
            for(int i=1; i<=N; i++) {
                if(area[i] == 1)
                    area1 += arr[i];
                else
                    area2 += arr[i];
            }
            visit = new boolean[N+1];
            
            int rs = 0;
            for(int i=1; i<=N; i++) {
                if(!visit[i]) {
                    checkArea(i, area[i]);
                    rs++;
                }
            }
            if(rs == 2) {
                if(minValue > Math.abs(area1 - area2))
                    minValue =  Math.abs(area1 - area2);
            }
            return;
        }
        
        area[count] = 1;
        dfs(count+1);
        
        area[count] = 2;
        dfs(count+1);
    }
    private static void checkArea(int index, int num) {
        // TODO Auto-generated method stub
        visit[index] = true;
        for(int i=1; i<=N; i++) {
            if(connect[index][i] == 1 && !visit[i] && area[i]==num)
                checkArea(i, num);
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_17070 파이프 옮기기1 - Java 자바  (0) 2020.03.19
#백준_16637 괄호 추가하기  (0) 2020.03.18
#백준_17281 ⚾ - Java 자바  (0) 2020.03.16
#백준_1986 체스 - Java 자바  (1) 2020.03.12
#백준_12761 돌다리 - Java 자바  (0) 2020.03.11

# 유형 : 탐색+시뮬레이션, DFS, 순열

# 난이도 : 골드 4

# 1번 선수를 4번 타자로 미리 결정하였기 때문에 4번을 1번선수로 고정하고, 나머지 1~3번 5~9번을 순열을 돌려 가장 높은 값을 얻을 때까지 게임을 진행해야 한다. 

 

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
94
95
96
97
98
99
100
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p17281 {
    static int N, maxValue = 0;
    static int arr[][];
    static int check[];
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][9];
        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        check = new int[9];
        
        //좋아하는 선수인 1번 선수를 4번 타자로 미리 결정
        check[3] = 0;
        
        dfs(0);
        System.out.println(maxValue);
        
        
    }
    public static void dfs(int count) {
        if(count == 3) {
            dfs(count+1);
            return;
        }
        
        if(count == 9) {
            int temp = solve();
            maxValue = Math.max(maxValue, temp);
            return;
        }
        
        else {
            for(int n=1; n<9; n++) {
                boolean is = false;
                for(int i=0; i<count; i++) {
                    if(check[i] == n) {
                        is = true;
                        break;
                    }
                }
                
                if(is)
                    continue;
                check[count] = n;
                dfs(count+1);
            }
        }
    }
    private static int solve() {
        
        int result = 0;
        int index = 0;
        
        for(int i=0; i<N; i++) {
            boolean base[] = new boolean[4];
            base[0] = true;
            
            for(int j=0; j<3; j++) {
                int val = arr[i][check[index]];
                if(val == 0) {
                    index++;
                    index%=9;
                }else {
                    for(int bs=3; bs>=0; bs--) {
 
                        if(base[bs]) {
                            if(bs+val >= 4) {
                                result++;
                                base[bs] = false;
                            }
                            else {
                                base[bs+val] = true;
                                base[bs] = false;
                            }
                        }
                    }
                    base[0] = true;
                    index++;
                    index%=9;
                    j--;
                }
            }
        }
        // TODO Auto-generated method stub
        return result;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_16637 괄호 추가하기  (0) 2020.03.18
#백준_17471 게리맨더링 - Java 자바  (0) 2020.03.17
#백준_1986 체스 - Java 자바  (1) 2020.03.12
#백준_12761 돌다리 - Java 자바  (0) 2020.03.11
#백준_2986 파스칼 - Java 자바  (0) 2020.03.11

+ Recent posts

티스토리툴바