[이것이 코딩 테스트다 with Python] 블록 이동하기(Java)
Goal
“이것이 코딩 테스트다 with Python” 교재의 문제를 분석하고 코드와 함께 이해해보기 위한 글입니다.
문제 분석
복잡한 구현과 BFS가 필요한 문제입니다.
복잡한 구현을 요하기 때문에 코드 설명으로 분석을 마칩니다.
먼저 전역변수입니다.
전역변수
map[][]: 지도값을 저장할 배열n: 지도의 크기dx, dy: 상하좌우로 이동하는데에 쓸 배열row: 로봇이 가로로 움직일 때 방문여부를 저장할 배열col: 로봇이 세로로 움직일 때 방문여부를 저장할 배열answer: 목적지까지 걸린 시간
메소드
int solution: 전역 변수들을 초기화해주고 로봇 처음 위치를 방문처리한 후 로봇을 이동시키는 BFS 작업을 하는void start를 호출해 답을 돌려줍니다.void start: 처음 위치부터 ‘로봇이 한번 BFS를 마치면dir값이-1이 되도록 Queue를 세팅’ 해주고 dir값이-1일 때마다 cnt(시간)을 올려줍니다. BFS는 로봇이 이동할 수 있는, 회전할 수 있는 칸인지 확인하고 확인 결과 가능하다면 방문처리한 후 Queue에 추가합니다.boolean rotate: 로봇이 회전 시에 위치할 좌표 값을 받아boolean check를 호출합니다.boolean check: 받은 좌표가 맵을 벗어나지 않고 로봇이 위치할 수 있는 곳인지 확인합니다.
클래스
Robot: 로봇이 위치하는Point와 가로(0), 세로(1)인지 저장하는 dir 를 필드로 갖습니다.Point: 좌표값을 필드로 갖습니다.
코드 구현
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
class Solution { //p355
private static int map[][];
private static int n;
private static int dx[] = {-1, 1, 0, 0};
private static int dy[] = {0, 0, -1, 1};
private static boolean[][] row;
private static boolean[][] col;
private static int answer;
static class Robot {
Point p1, p2;
int dir; // 가로: 0, 세로: 1
public Robot(Point p1, Point p2, int dir) {
this.p1 = p1;
this.p2 = p2;
this.dir = dir;
}
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public int solution(int[][] board) {
n = board.length;
answer = 0;
row = new boolean[n][n];
col = new boolean[n][n];
map = new int[n][n];
for (int i = 0; i < n; i++) {
map[i] = board[i].clone();
}
row[0][0] = true;
row[0][1] = true;
start();
return answer;
}
private static void start() {
Queue<Robot> q = new LinkedList<>();
q.add(new Robot(new Point(0, 0), new Point(0, 1), 0));
q.add(new Robot(null, null, -1));
int cnt = 0;
while (!q.isEmpty()) {
Robot now = q.poll();
if (now.dir == -1) {
cnt++;
if (!q.isEmpty()) {
q.add(new Robot(null, null, -1));
} continue;
}
if ((now.p1.x == n - 1 && now.p1.y == n - 1) || (now.p2.x == n - 1 && now.p2.y == n - 1)) {
answer = cnt;
break;
}
if (now.dir == 0) {
for (int i = 0; i < 4; i++) {
int nx1 = now.p1.x + dx[i];
int ny1 = now.p1.y + dy[i];
int nx2 = now.p2.x + dx[i];
int ny2 = now.p2.y + dy[i];
if (check(nx1, ny1) && check(nx2, ny2)) {
if (!row[nx1][ny1] || !row[nx2][ny2]) {
Robot next = new Robot(new Point(nx1, ny1), new Point(nx2, ny2), 0);
row[nx1][ny1] = true;
row[nx2][ny2] = true;
q.add(next);
}
}
}
for(int i = -1; i <= 1; i+=2) {
int nx1 = now.p1.x + i;
int ny1 = now.p1.y;
int nx2 = now.p2.x + i;
int ny2 = now.p2.y;
if (check(nx1, ny1) && check(nx2, ny2)) {
if (rotate(nx1, ny1, now.p1.x, now.p1.y) && (!col[nx1][ny1] || !col[now.p1.x][now.p1.y])) {
col[nx1][ny1] = true;
col[now.p1.x][now.p1.y] = true;
q.add(new Robot(new Point(nx1, ny1), new Point(now.p1.x, now.p1.y), 1));
}
if (rotate(nx2, ny2, now.p2.x, now.p2.y) && (!col[nx2][ny2] || !col[now.p2.x][now.p2.y])) {
col[nx2][ny2] = true;
col[now.p2.x][now.p2.y] = true;
q.add(new Robot(new Point(nx2, ny2), new Point(now.p2.x, now.p2.y), 1));
}
}
}
} else {
for (int i = 0; i < 4; i++) {
int nx1 = now.p1.x + dx[i];
int ny1 = now.p1.y + dy[i];
int nx2 = now.p2.x + dx[i];
int ny2 = now.p2.y + dy[i];
if (check(nx1, ny1) && check(nx2, ny2)) {
if (!col[nx1][ny1] || !col[nx2][ny2]) {
Robot next = new Robot(new Point(nx1, ny1), new Point(nx2, ny2), 1);
col[nx1][ny1] = true;
col[nx2][ny2] = true;
q.add(next);
}
}
}
for(int i = -1; i <= 1; i+=2) {
int nx1 = now.p1.x;
int ny1 = now.p1.y + i;
int nx2 = now.p2.x;
int ny2 = now.p2.y + i;
if (check(nx1, ny1) && check(nx2, ny2)) {
if (rotate(nx1, ny1, now.p1.x, now.p1.y) && (!row[nx1][ny1] || !row[now.p1.x][now.p1.y])) {
row[nx1][ny1] = true;
row[now.p1.x][now.p1.y] = true;
q.add(new Robot(new Point(nx1, ny1), new Point(now.p1.x, now.p1.y), 0));
}
if (rotate(nx2, ny2, now.p2.x, now.p2.y) && (!row[nx2][ny2] || !row[now.p2.x][now.p2.y])) {
row[nx2][ny2] = true;
row[now.p2.x][now.p2.y] = true;
q.add(new Robot(new Point(nx2, ny2), new Point(now.p2.x, now.p2.y), 0));
}
}
}
}
}
}
public static boolean rotate(int x1, int y1, int x2, int y2) {
if (!check(x1, y1) || !check(x2, y2)) return false;
return true;
}
public static boolean check(int x, int y) {
return x >= 0 && y >= 0 && x < n && y < n && map[x][y] == 0;
}
}
This post is licensed under CC BY 4.0 by the author.