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

# 난이도 : 골드 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

+ Recent posts