16926번: 배열 돌리기 1
크기가 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
입력으로 들어오는 배열을 이런식으로 회전시킨 결과를 출력하는 문제입니다..
무작정 짜보려고 했다가 소스만 두번정도 갈아엎고 찾은 솔루션이 dfs 방법입니다.
바깥쪽 그룹부터 안쪽 그룹 순서대로 회전하기때문에 시작지점은 항상 (i, i)입니다.
우선 가장 바깥쪽 그룹부터 구간을 (0, 0) ~ (N - 1, M - 1)으로 잡고 R번 회전 시킨 후에
구간을 (+1, +1), ~ (-1, -1)씩 하고 다음 그룹도 똑같이 회전시켜줍니다. (구간 범위가 벗어나면 break)
dfs에서는 방문처리를 count식으로 방문 횟수를 갱신하였습니다.
next가 범위를 벗어나면 방향을 바꾸고 next를 다시 구해줍니다.
만약 next의 방문횟수와 자신의 방문횟수가 같으면 한바퀴를 돌았다는 뜻이 됩니다.
=> list[x][y]에 list[nx][ny]를 넣고 원래 자신의 값을 리턴합니다.
그러면 이제 리턴되는 값들을 모두 받게되면 회전 1번을 하게 된것입니다.
그리고 회전시킬 때 회전시키는 배열의 크기 (n - 1) * 2 + (m - 1) * 2번이 한바퀴이므로 mod 연산을 통해 R을 낮춰준 후에 회전시켜줍니다. 다음 구간으로 넘어가면 크기를 2만큼 줄여줘야합니다.
|
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
|
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 17406 배열 돌리기 4 (0) | 2021.02.10 |
|---|---|
| boj 16927 배열 돌리기 2 (0) | 2021.02.10 |
| boj 1068 트리 (0) | 2021.02.09 |
| boj 9202 Boggle (0) | 2021.02.02 |
| boj 15666 N과 M (12) (0) | 2021.01.31 |