728x90
https://www.acmicpc.net/problem/17822
17822번: 원판 돌리기
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀
www.acmicpc.net
처음 아이디어 : 시뮬레이션 문제로 조건을 다 구현해주면서 풀었다.
추가 : bfs 문제 + rotation 함수 사용
결론 : 시뮬 + bfs 문제라고 한다
|
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
|
import java.util.*;
import java.io.*;
public class Main {
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]+" ");
}
// System.out.println();
}
// 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);
br.close();
}
//
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++) {
Arrays.fill(tcir[i], -1);
}
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];
}
}
}
}
}
}
|
cs |
728x90
'알고리즘' 카테고리의 다른 글
| SWEA ::[모의 SW 역량테스트] 보호 필름 (0) | 2021.05.02 |
|---|---|
| SWEA ::[모의 SW 역량테스트] 디저트카페 (0) | 2021.05.02 |
| SWEA ::[모의 SW 역량테스트] 탈주범 검거 (0) | 2021.05.02 |
| SWEA :: [모의 SW 역량테스트] 등산로 조성 (0) | 2021.05.02 |
| BOJ :: 4485 녹색 옷 입은 애가 젤다지? (0) | 2021.05.02 |