문제 URL : 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
문제 접근법 :
bfs문제인데 이동은 좌우상하 이동하는것은 쉽지만 회전이 문제입니다. 회전을 어떻게 해야하는지 설명보단
그림이 더 이해하기 쉽겠죠?
자 보세여 이런모습일때 위아래로 움직였을때의 결과입니다.
움직이는것 자체는 쉽습니다. 왼쪽으로 이동이나 오른쪽의 이동도 충분히 상상할수 있는 모습일거라 생략하겠습니다. 자그럼 회전을 확인해보죠
이그림을 보고 회전의 모양도 그림으로 잘유추할수있습니다. 그렇지만 어떻게 회전을 진행해야 하는건지 아직은 잘알수가없습니다. 하지만 잘보시면 두그림의 공통점이있습니다.
잘보시면 저기 노란색지점이 하나라도 벽이라면 위그림과 같이 회전도 안되고 이동조차 안됩니다.
즉이것을 바꿔얘기하면 위로 이동이 가능하다는것은 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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
#define vvvi v<vvi>
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n;
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < n;
}
int bfs(vvi& board) {
n = board.size();
vvvi visit(4, vvi(n, vi(n)));
queue<tuple<int, int, int, int>> q;
q.push({ 1,0,0,0 });
visit[1][0][0] = 1;
int res = 0;
while (!q.empty()) {
int dir, y1, x1, cnt, y2, x2;
tie(dir, y1, x1, cnt) = q.front();
q.pop();
tie(y2, x2) = make_tuple(y1 + dy[dir], x1 + dx[dir]);
res = cnt;
if ((y1 == n - 1 && x1 == n - 1) || (y2 == n - 1 && x2 == n - 1)) return cnt;
//좌우상하 이동
for (int i = 0; i < 4; i++) {
int ny1, nx1, ny2, nx2;
tie(ny1, nx1, ny2, nx2) = make_tuple(y1 + dy[i], x1 + dx[i], y2 + dy[i], x2 + dx[i]);
if (!isrange(ny1, nx1) || !isrange(ny2, nx2))continue;
if (visit[dir][ny1][nx1] || board[ny1][nx1] || board[ny2][nx2])continue;
q.push({ dir,ny1,nx1,cnt + 1 });
visit[dir][ny1][nx1] = 1;
}
//회전
int r[2] = { 1,3 };
for (int i : r) {
int ndir = (dir + i) % 4;
int ny1, nx1, ny2, nx2;
tie(ny1, nx1, ny2, nx2) = make_tuple(y1 + dy[ndir], x1 + dx[ndir], y2 + dy[ndir], x2 + dx[ndir]);
if (!isrange(ny1, nx1) || !isrange(ny2, nx2))continue;
//이동이 가능한건지
if (board[ny1][nx1] || board[ny2][nx2])continue;
if (visit[ndir][y1][x1] == 0) {
q.push({ ndir,y1,x1 ,cnt+1});
visit[ndir][y1][x1] = 1;
}
if (visit[ndir][y2][x2] == 0) {
q.push({ ndir,y2,x2 ,cnt + 1 });
visit[ndir][y2][x2] = 1;
}
}
}
return res;
}
int solution(vector<vector<int>> board) {
int answer = 0;
return bfs(board);
}
|
cs |
근데 저는여기서 궁금한점이있는데 처음 코드를 짰을때 이동을한후 이동이가능하니 회전을 함께하는 코드로 짰었는데
테스트 케이스 6번만 틀리더군요 한참 고민해도 답을 못내서 이동을 먼저하고 회전을 나중에했는데
답이 맞았는데 왜 그렇게해야 답이맞는지는 잘모르겠더군요...
반드시 회전을 나중에해야하는 이유라도 있는건지 반례테스트케이스를 잘 못찾겠어서 ㅠ.ㅠ 6번테스트케이스가 너무 궁금합니당
궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.
공감 눌러주실꺼죠??
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 블록 게임(2019 KAKAO BLIND RECRUITMENT) (0) | 2021.09.04 |
|---|---|
| 프로그래머스 매칭 점수(2019 KAKAO BLIND RECRUITMENT) (0) | 2021.09.01 |
| 프로그래머스 가사 검색(2020 KAKAO BLIND RECRUITMENT) (0) | 2021.08.23 |
| 프로그래머스 [3차] 압축(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.08.19 |
| 프로그래머스 [3차]파일명 정렬(2018 KAKAO BLIND RECRUITMENT) (0) | 2021.08.19 |
