16927번: 배열 돌리기 2
크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5]
www.acmicpc.net
boj 16926 배열 돌리기 1
www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ←..
emoney96.tistory.com
위의 문제풀이와 동일합니다.
이 문제는 많은 회전으로 인한 TLE가 발생할 수 있는 문제였지만 저는 이전문제에서 이미 해줬던 부분이라 바로 AC를 받았습니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int visit[][];
static int list[][];
static int N, M, R;
static int sx, sy, ex, ey;
static void print() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sb.append(list[i][j] + " ");
}
sb.append("\n");
}
System.out.println(sb.toString());
}
static int dfs(int x, int y, int idx) {
visit[x][y]++;
int nx = x + direct[idx][0];
int ny = y + direct[idx][1];
if (nx < sx || ny < sy || nx > ex || ny > ey) {
idx++;
nx = x + direct[idx][0];
ny = y + direct[idx][1];
}
if (visit[nx][ny] == visit[x][y]) {
int tmp = list[x][y];
list[x][y] = list[nx][ny];
return tmp;
}
int tmp = list[x][y];
list[x][y] = dfs(nx, ny, idx);
return tmp;
}
static void solve() {
sx = 0;
sy = 0;
ex = N - 1;
ey = M - 1;
int n = N;
int m = M;
for (int i = 0;; i++) {
for (int j = 0; j < R % ((n - 1) * 2 + (m - 1) * 2); j++) {
dfs(i, i, 0);
}
sx++;
sy++;
ex--;
ey--;
n -= 2;
m -= 2;
if (sx > ex || sy > ey)
break;
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
list = new int[N][M];
visit = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
solve();
print();
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 3109 빵집 (0) | 2021.02.18 |
|---|---|
| boj 17406 배열 돌리기 4 (0) | 2021.02.10 |
| boj 16926 배열 돌리기 1 (0) | 2021.02.10 |
| boj 1068 트리 (0) | 2021.02.09 |
| boj 9202 Boggle (0) | 2021.02.02 |