알고리즘40 :: BOJ_17822_원판돌리기
|
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
package backjun;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.StringTokenizer;
class Pos{
int first;
int second;
Pos(int first, int second){
this.first = first;
this.second = second;
}
}
public class 원판돌리기 {
private static int n,m,rot,x,d,k;
private static ArrayList<Pos> group = new ArrayList<>();
private static int[][] a;
private static boolean range(int x, int y) {
if(1<=x && x<n+1 && 0<=y && y<m) return true; else return false;
}
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); rot = Integer.parseInt(st.nextToken());
a = new int[n+1][m];
for(int i=1; i<n+1; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<m; j++) {
a[i][j] = Integer.parseInt(st.nextToken());}}//end of for loop
for(int r=1; r<=rot; r++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken()); d = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken());
//1step :: 돌려야할 원판 고르고 회전시키기 + 0은 시계방향, 1은 반시계 방향
for(int i=1; i<n+1; i++) { //돌려야 하는 원판
if(i%x==0) {
for(int j=1; j<=k; j++) { //몇번 회전 시킬건지
if(d==0) {
//시계방향
int temp = a[i][m-1];
int c = m-2;
for(int u=m-1; u>=1; u--) {
a[i][u] = a[i][c];
c-=1;
} a[i][0] = temp;
}else {
//반시계방향
int temp = a[i][0];
int c = 1;
for(int u=0; u<m-1; u++) {
a[i][u] = a[i][c];
c+=1;
}a[i][m-1] = temp;
}}}}//end of for loop
//step2 :: 인접한 수 지우기, 없다며 평균 구해서 평균보다 작으면 +1 / 크면 -1 을 해준다.
/*
* (i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
*/
boolean find = false; //인접 한 경우가 없다면 false 유지;
for(int i=1; i<=n; i++) {
for(int j=0; j<m; j++) {
//(i, 1)은 (i, 2), (i, M)과 인접하다.
if(a[i][j] == 0) continue;
if(j==0 && range(i,j+1)) {
if(a[i][j] == a[i][j+1]) {
group.add(new Pos(i,j));
group.add(new Pos(i,j+1));
}
if(a[i][j] == a[i][m-1]) {
group.add(new Pos(i,j));
group.add(new Pos(i,m-1));
}}
//(i, M)은 (i, M-1), (i, 1)과 인접하다. => 1case에 대해서 순차적으로 처리하므로
if(j==m-1 && range(i,j-1)){
if(a[i][j] == a[i][j-1]) {
group.add(new Pos(i,j));
group.add(new Pos(i,j-1));
}
if(a[i][j] == a[i][0]) {
group.add(new Pos(i,j));
group.add(new Pos(i,0));
}}
//(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) => 1case에 대해서 순차적으로 처리
if(j>=2 && j<=m-1 && range(i,j-1) && range(i,j+1)) {
if(a[i][j] == a[i][j-1]) {
group.add(new Pos(i,j));
group.add(new Pos(i,j-1));
}
if(a[i][j] == a[i][j+1]) {
group.add(new Pos(i,j));
group.add(new Pos(i,j+1));
}}
//(1, j)는 (2, j)와 인접하다.
if(i==0 && range(i+1,j)) {
if(a[i][j] == a[i+1][j]) {
group.add(new Pos(i,j));
group.add(new Pos(i+1,j));
}}
//(N, j)는 (N-1, j)와 인접하다.
if(i==n && range(i-1,j)) {
if(a[i][j] == a[i-1][j]) {
group.add(new Pos(i,j));
group.add(new Pos(i-1,j));
}}
//(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
if(2<=i && i<=n-1 && range(i-1,j) && range(i+1,j)) {
if(a[i][j] == a[i-1][j]) {
group.add(new Pos(i,j));
group.add(new Pos(i-1,j));
}
if(a[i][j] == a[i+1][j]) {
group.add(new Pos(i,j));
group.add(new Pos(i+1,j));
}}
}}//end of for loop
if(group.size()==0) {
int sum = 0;
int cnt = 0;
for(int i=1; i<=n; i++) {
for(int j=0; j<m; j++) {
if(a[i][j]==0) continue;
else {
sum+=a[i][j]; cnt+=1;
}
}}
double d = (double)sum/cnt;
for(int i=1; i<n+1; i++) {
for(int j=0; j<m; j++) {
if(a[i][j] == 0) continue;
if(a[i][j]>d) {
a[i][j]-=1;
}else if(a[i][j]<d) {
a[i][j]+=1;
}
}}
}else {
for(int i=0; i<group.size(); i++) {
if(a[group.get(i).first][group.get(i).second]==0) continue;
else
a[group.get(i).first][group.get(i).second]=0;
}}
group.clear();
}
int ans = 0;
for(int i=1; i<=n; i++) {
for(int j=0; j<m; j++) {
ans+=a[i][j];
}}
System.out.println(ans);
}
}
|
cs |
시뮬레이션 문제로 조건을 다 구현해주면 풀렸다.
추가적으로 시계, 반시계 방향으로 돌릴때 다음처럼 구현해주면 뭔가 더 멋지다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
private static void turn(int i) {
int temp[] = new int[k[i]];
for (int j = x[i], x = 1; j * x <= n; x++) {
int o = j * x - 1;
switch(d[i]) {
case 0:
System.arraycopy(board[o], m - k[i], temp, 0, k[i]);
System.arraycopy(board[o], 0, board[o], k[i], m - k[i]);
System.arraycopy(temp, 0, board[o], 0, k[i]);
break;
case 1:
System.arraycopy(board[o], 0, temp, 0, k[i]);
System.arraycopy(board[o], k[i], board[o], 0, m - k[i]);
System.arraycopy(temp, 0, board[o], m - k[i], k[i]);
break;
default: return;
}
}
}
|
cs |
백준에서 가장 빠른 시간내로 푸신분의 코드 중 일부를 들고와봤다.
https://www.acmicpc.net/source/16397738
로그인
www.acmicpc.net
System.arraycopy(src,시작,dest,시작,len); 으로 src 배열에서 시작 index부터 len 길이만큼 dest 배열에서 시작 index에서 len 길이만큼 복사한다.
|
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
package algo;
public class Main_17822_원판돌리기 {
static int cir[][], n, m, t;
static int[] di = { -1, 1, 0, 0 };
static int[] dj = { 0, 0, -1, 1 };
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 원판의 크기
m = Integer.parseInt(st.nextToken()); // 각 원판의 정점 갯수
t = Integer.parseInt(st.nextToken()); // t번 회전 시킴
cir = new int[n][m]; // 원판
int x = 0;
int d = 0;
int k = 0;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
cir[i][j] = Integer.parseInt(st.nextToken());
// System.out.print(cir[i][j]+" ");
}
}
// t번 돌리자
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine());
x = Integer.parseInt(st.nextToken()); // x배수 원판을 돌리자
d = Integer.parseInt(st.nextToken()); // 0 시계 1 반시계
k = Integer.parseInt(st.nextToken()); // k 칸 돌림
start(x, d, k);
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans += cir[i][j];
}
}
System.out.println(ans);
}
//
static void start(int nx, int nd, int nk) {
int temp = 0;
for (int i = 1; i <= nk; i++) { // 몇 바퀴 돌릴꺼 ?
for (int j = 1;; j++) {
// x 배수 원판을 돌리자
int a = j * nx;
// 원판 크기 보다 커지면 멈춤
if (a > n)
break;
// 시계 방향
if (nd == 0) {
for (int k = m-1; k > 0; k--) {
temp = cir[a -1][k];
cir[a - 1][k] = cir[a - 1][k - 1];
cir[a - 1][k - 1] = temp;
}
} else { // 반시계
for (int k = 0; k < m - 1; k++) {
temp = cir[a -1][k];
cir[a - 1][k] = cir[a - 1][k + 1];
cir[a - 1][k + 1] = temp;
}
}
}
}
find();
}
static void find() {
// 탐색
int sum = 0; // 원판의 총합
boolean chk = false; // true이면 인접한 수 중 같은 수가 있을 때 / false면 같은 수가 없을 때
int cnt = 0; // chk가 false일때 써먹을거 0이 아닌 수가 몇개 인지 찾음
int[][] tcir = new int[n][m];// temp map
for (int i = 0; i < n; i++) {
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(cir[i][j] != 0) {
cnt++;
}
sum += cir[i][j]; // 현재 위치 0 이면 패스
for (int k = 0; k < 4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni < 0)
continue;
if (ni >= n)
continue;
if (nj < 0) { // 1번 정점과 마지막 정점을 비교 해줌
if (cir[ni][m - 1] == cir[ni][0]
&& (cir[ni][m - 1] != 0 && cir[ni][0] != 0)) {// 한번도 변한적 없는 것만 바꿔 주자
tcir[ni][m - 1] = 0;
tcir[ni][0] = 0;
chk = true;
}
}
if (nj >= m) // 위에 마지막 정점은 1번 정점과 비교해줬음
continue;
//위에서 예외는 다 처리해줬으니 그냥 찾아 보자
if (ni >= 0 && nj >= 0 && ni < n && nj < m
&& (cir[i][j] != 0 && cir[ni][nj] != 0)) {// 한번도 변한적 없는 것만 바꿔 주자
if (cir[i][j] == cir[ni][nj]) {
tcir[i][j] = 0;
tcir[ni][nj] = 0;
chk = true;
}
}
}
}
}
// 인접한 정점에 같은것이 하나도 없었을때
if (!chk) {
float avg = (float)sum / cnt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((float)cir[i][j] > avg && cir[i][j] != 0) {
cir[i][j] -= 1;
} else if ((float)cir[i][j] < avg && cir[i][j] != 0) {
cir[i][j] += 1;
}else if((float)cir[i][j] == avg && cir[i][j] != 0){
continue;
}
}
}
// 인접한 정점에 같은것이 있었을 때
} else {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (tcir[i][j] == 0) {
cir[i][j] = tcir[i][j];
}
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
'알고리즘' 카테고리의 다른 글
| 알고리즘42 :: BOJ_15683_감시(java) (0) | 2019.12.12 |
|---|---|
| 알고리즘41 :: BOJ_14226_이모티콘 (0) | 2019.12.09 |
| 알고리즘39 :: BOJ_2933_미네랄 (0) | 2019.12.07 |
| 알고리즘38 :: swea_모의시험_벽돌깨기 (0) | 2019.11.11 |
| 알고리즘37 :: 정올_2615_오목 (0) | 2019.11.08 |