https://programmers.co.kr/learn/courses/30/lessons/60063
코딩테스트 연습 - 블록 이동하기 | 프로그래머스
[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7
programmers.co.kr
백준의 1938번 통나무 옮기기(문제 링크)와 비슷한 느낌의 BFS 문제다.
이게 조금 더 어려운 것 같기는 하다...
좌표를 어떻게 저장할까 하다가 아래 카카오 기술 블로그에 있는 해설에서 아이디어를 얻어서 풀었다.
https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/
2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설
올해에도 2020이라는 멋진 숫자와 함께, 카카오의 신입 개발자 채용을 시작했습니다! 그 여정 중 첫 단계로 1차 코딩 테스트가 지난 9월 7일 토요일 오후 2시부터 오후 7시까지 5시간 동안 진행됐는데요. 저희 준비위원들도 설렘과 긴장 속에 원활한 진행을 위해 노력했고, 무사히 1차 테스트를 마칠 수 있었습니다. 테스트에는 총 7문제가 출제됐고, 응시자는 5시간 이내에 순서와 상관없이 문제를 해결해야 […]
tech.kakao.com
위의 해설에
(r, c, d) : (r, c) 위치에서 d 방향에 있는 칸을 한 칸 더 차지하고 있음이라고 나와있어서
로봇의 x, y좌표, 방향, 시간을 구조체로 저장해 큐에 넣어서 BFS를 진행하였다.
로봇의 나머지 한 칸은 방향 정보를 이용하여 구한다.
매번 상, 하, 좌, 우로 이동하는 경우와
로봇의 두 칸 중 한 칸에서 시계방향으로 90도 회전하는 경우 / 반시계 방향으로 90도 회전하는 경우
나머지 한 칸에서 시계방향으로 90도 회전하는 경우 /반시계 방향으로 90도 회전하는 경우 중
이동 가능한 위치(벽이 아니고 범위를 벗어나지 않는 곳)를 계속 큐에 넣어주면서 진행하면 된다.
로봇을 이동시킬 때, 두 칸 중 한 칸만의 좌표를 기준으로 이동시키므로
로봇의 한 칸을 (x, y)라고 하고 다른 한칸을 (xx, yy)라고 했을 때, visit 배열을 (x, y)를 기준으로 방문을 확인하고 큐에도 (x, y)좌표와 (x, y) 기준의 방향이 들어간다.
따라서 (x, y)축을 기준으로 회전할때는 (x, y)의 좌표는 변화가 없고 방향만 변화하므로 새로 큐에 넣을 때도 (x, y) 좌표 그대로와 회전된 새 방향을 넣어준다.
반대로, (xx, yy)를 축으로 (x, y)를 회전한 경우에는 (x, y)를 이동시킨 위치인 (nx, ny)를 기준으로 만들어주기 위해서 방향을 반대로 바꿔주고 큐에 넣어줄 때에도 (xx, yy)가 아닌 (nx, ny) 좌표와 (nx, ny) 기준의 방향을 넣어준다.
|
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
|
#include <vector>
#include <queue>
using namespace std;
int n;
bool visit[100][100][4];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
//회전할 때 지나칠 곳
int ndx[] = { -1,1,1,-1 };
int ndy[] = { 1,1,-1,-1 };
struct Robot {
int x;
int y;
int dir;
int time;
Robot(int a, int b, int d, int t) {
x = a;
y = b;
dir = d;
time = t;
}
};
bool rangeCheck(int x, int y, int xx, int yy) {
if (x < 0 || x >= n || y < 0 || y >= n) return false;
if (xx < 0 || xx >= n || yy < 0 || yy >= n) return false;
return true;
}
int solution(vector<vector<int>> board) {
queue<Robot> q;
q.push(Robot(0, 0, 0, 0));
visit[0][0][0] = true;
n = board.size();
int destX = n - 1;
int destY = n - 1;
int cnt = 0;
while (!q.empty()) {
int x = q.front().x;
int y = q.front().y;
int dir = q.front().dir;
int time = q.front().time;
q.pop();
//로봇의 나머지 한칸
int xx = x + dx[dir];
int yy = y + dy[dir];
//로봇의 한칸이라도 도착하면 종료
if (x == destX && y == destY) return time;
if (xx == destX && yy == destY) return time;
int nx, ny, nxx, nyy;
//우, 하, 좌, 상 이동
for (int k = 0; k < 4; k++) {
nx = x + dx[k];
ny = y + dy[k];
nxx = xx + dx[k];
nyy = yy + dy[k];
//이동할 곳의 범위 체크
if (!rangeCheck(nx, ny, nxx, nyy)) continue;
//이동할 곳의 방문 체크
if (visit[nx][ny][dir]) continue;
//이동할 수 있는지 체크
if (board[nx][ny] == 1 || board[nxx][nyy] == 1) continue;
visit[nx][ny][dir] = true;
q.push(Robot(nx, ny, dir, time + 1));
}
//x,y 를 축으로 90도 회전
for (int i = 1; i < 4; i += 2) {
int ndir = (dir + i) % 4;
nxx = x + dx[ndir];
nyy = y + dy[ndir];
int rx, ry; //회전하면서 지나갈 곳의 좌표
if (i == 1) {
//시계방향 회전인 경우
rx = x + ndx[ndir];
ry = y + ndy[ndir];
}
else {
//반시계방향 회전인 경우
rx = x + ndx[dir];
ry = y + ndy[dir];
}
if (!rangeCheck(rx, ry, nxx, nyy)) continue;
if (visit[x][y][ndir]) continue;
if (board[nxx][nyy] == 1) continue;
if (board[rx][ry]) continue;
visit[x][y][ndir] = true;
q.push(Robot(x, y, ndir, time + 1));
}
//xx, yy 를 축으로 90도 회전
dir = (dir + 2) % 4; //xx, yy가 기준이므로 방향이 반대로 바뀐다.
for (int i = 1; i < 4; i += 2) {
int ndir = (dir + i) % 4;
nx = xx + dx[ndir];
ny = yy + dy[ndir];
int rx, ry; //회전하면서 지나갈 곳의 좌표
if (i == 1) {
//시계방향 회전인 경우
rx = xx + ndx[ndir];
ry = yy + ndy[ndir];
}
else {
//반시계방향 회전인 경우
rx = xx + ndx[dir];
ry = yy + ndy[dir];
}
if (!rangeCheck(nx, ny, rx, ry)) continue;
if (board[nx][ny] == 1) continue;
if (board[rx][ry] == 1) continue;
ndir = (ndir + 2) % 4;
if (visit[nx][ny][ndir]) continue;
visit[nx][ny][ndir] = true;
q.push(Robot(nx, ny, ndir, time + 1));
}
}
}
Colored by Color Scripter
|
'프로그래머스' 카테고리의 다른 글
| 2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ ) (0) | 2020.04.08 |
|---|---|
| 프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++ (1) | 2020.03.11 |
| 프로그래머스 [2020카카오공채] 괄호 변환 c++ (0) | 2019.10.17 |
| 프로그래머스 [2020카카오공채] 문자열 압축 c++ (0) | 2019.10.17 |
| 프로그래머스 - 소수 찾기 (0) | 2019.10.04 |