프로그래머스의 블록이동하기(Lv3) 문제이다.
[ 문제풀이 ]
가장 초기의 로봇이 주어졌을 때, 로봇을 움직이고 회전시키면서 (N , N) 좌표까지 갈 때 걸리는 최소 시간을 구해야 하는 문제이다. 문제를 풀기 위한 변수들을 선언하는 과정부터 정답을 도출하는 과정까지 진행해보자.
#1. 변수선언 및 전체적인 접근법
이 문제는 최소시간을 구해야 하는 문제이기 때문에 본인은 완전탐색을 이용해서 접근하였다. 완전탐색중에서도 너비우선탐색(BFS)을 이용해서 접근해 보았다.
BFS탐색은 Queue를 이용해서 데이터를 관리하면서 최단시간을 구할 수 있다. 그렇다면 이 문제에서 BFS탐색을 하기 위해서 사용되는 Queue에는 어떤 정보들이 관리되어야 하는지부터 알아보자.
#1 - 1) 좌표정보
가장 먼저 골치아픈게 로봇이 2칸을 차지하고 있는 형태라는 것이다. 단순히 한칸만 차지 하고 있다면, 해당 로봇이 차지하는 좌표의 (x , y)만 알면 될텐데... 골치아프게 로봇이 2칸을 차지하고 있다. 그렇다면 이 2칸에 대한 좌표정보들을 모두 알고있어야 할까 ??? 그런 방법도 있을 것이다. 그런데 본인은 그렇게 하지 않고 로봇이 차지 하는 칸 중에서 한 칸에 대한 좌표정보만을 저장해서 관리해 주었다. 그렇다면 로봇이 차지하는 2칸 중 어느 칸을 저장해서 관리해 주어야 할까 ?? 본인은 무조건적으로 2칸 중 (N , N)에 더 가까운 칸 하나만을 넣어서 관리해 주었다.
예를 들면 다음과 같다.
위의 그림을 보게되면 나올 수 있는 로봇이 서로 다른 위치에 다른 모양으로 있는 형태를 대략적으로 그려본 것이다.
그리고 로봇들 중에서 "파랑색 점이 찍힌 좌표" 가 있다는 것을 확인할 수 있다.
본인이 위에서 이야기한 "관리할 좌표정보"가 파랑색 점이 찍힌 좌표들이다. 파랑색 점이 찍힌 좌표들을 보게되면 다음과 같은 공통점이 하나 있다.
"로봇이 차지하고 있는 2개의 좌표 중, (N , N)에 상대적으로 더 가까운 좌표들" 이라는 것이다.
지금부터 간단하게 로봇이 차지하고 있는 2개의 좌표 중, (N , N)에 상대적으로 더 가까운 좌표를 "기준이 되는 좌표" 라고 간략하게 줄여서 말하겠다.
그렇다면 우리는 이 한칸을 이용해서 다른 한 칸의 위치정보 또한 알 수 있도록 만들어야 할 것이다. 왜냐하면 하나의 예를 들어서 내가 (1 , 1)에 로봇이 있다고 저장을 해놨다면, 로봇이 현재 가로형태로 (1 , 0) - (1 , 1) 에 있는지,
(1 , 1) - (1 , 2) 에 있는지 아니면 세로형태로 (0 , 1) | (1 , 1) 에 있는지, (1 , 1) | (2 , 1)에 있는지 모를 것이기 때문이다. 그래서 본인은 "방향 정보"를 넣어주었다. 방향 정보라는 것이 어떤 말일까 ??
위에서 본인은 로봇이 차지하고 있는 2개의 좌표 중, 상대적으로 (N , N)에 더 가까운 좌표만을 저장해 두었다고 했다.
이 좌표를 (x , y)라고 표기하겠다. 그렇다면 상대적으로 (N , N)에 더 먼 좌표가 또 하나 있을 것이다. 이 좌표를 (xx , yy) 라고 표기하겠다. 이 (xx , yy)는 (x , y)를 기준으로 무조건 상하좌우 중 한 방향에는 존재할 것이다. 왜냐하면 로봇이 대각선으로 존재하는 그런 형태는 없기 때문이다. 즉 ! 이 (xx , yy)가 (x , y)를 기준으로 어느 방향에 존재하는지만 알면, 로봇의 형태는 물론 로봇이 차지하고 있는 2개의 좌표에 대해서 알 수 있을 것이다.
#1 - 2) 중복 제거를 위한 방문표시
완전탐색에서 탐색을 할 때 중요한 것중 하나가 중복 탐색을 방지하기 위해서 이미 한번 탐색한 데이터에 대해서는 탐색했다고 표시를 해주는 것이 중요하다. 이 문제처럼 좌표가 주어지고, 좌표들 위에서 이리저리 움직이는 경우에는 보통 "해당 좌표를 이전에 방문했습니다, 안했습니다" 로 방문처리를 해줄 수 있다. 그렇다면 우리는 위에서 로봇이 차지하는 2개의 좌표 중, 하나의 좌표만 가지고 정보를 다루기로 했으니, 해당 좌표만 방문했다 안했다로 표시를 해주면 될까 ??
만약 그렇게 했다고 가정했을 때, 아래와 같은 상황을 한번 보자.
위의 왼쪽 그림과 같이 로봇이 존재할 때, 파랑색 점에 있는 로봇을 기준으로 위쪽으로 90도 회전을 시켰다고 가정해보자.
그럼 로봇이 오른쪽 그림과 같은 형태가 될 것이고, 왼쪽의 로봇과는 확연하게 다른 형태 그리고 다른 모양이 된다.
그렇다면 기존에 로봇이 있었던 맵에서 파랑색 점이 찍힌, 즉, 우리가 관리할 좌표를 (x , y)라고 가정해보자.
문제는 오른쪽 그림에서 나타난다. 오른쪽 그림에서도 상대적으로 (N , N)에 더 가까운 로봇의 좌표가 (x , y)가 되어버리기 때문에, 단순히 우리가 관리하는 좌표를 방문했다 or 안했다로 관리하게 되면 위와 같은 상황은 발생할 수 없을 것이다. 더 큰 문제는 위와 같은 상황이 필연적으로 이루어져야만 정답이 가능한 경우도 있을 수 있다는 것이다.
즉 ! 단순히 우리가 관리하는 좌표를 방문했다 안했다로 중복처리를 하기에는 조금 부족한 상황이 존재하게 된다.
그래서 방문처리 또한 "방향의 개념"을 집어 넣어서 처리해 주었다.
즉 ! 왼쪽 그림같은 경우에는 "(x , y)에서 서쪽에 로봇이 있는 형태를 탐색했습니다" 가 되는 것이고,
오른쪽 그림같은 경우에는 "(x , y)에서 북쪽에 로봇이 있는 형태를 탐색했습니다" 가 되는 것이다.
이렇게 되면 2개는 똑같이 (x , y)라는 기준좌표를 가지고 있지만, 서로 다른 탐색이 되어버리게 된다.
이를 3차원 배열로 표현해 주었다. 아래의 코드에서 나올테지만 bool Visit[][][] 라는 3차원 배열을 사용해서 이를 관리해 주었다. Visit[a][b][c] = true 의 의미는 "(x , y)에 기준좌표가 있고, 로봇이 (x , y)에서 c의 방향으로 존재하는 형태는 탐색했습니다" 를 의미하게 된다.
#1 - 3) 정리.
Queue에 들어가는 정보들을 알기 위해서 1 - 1과 1 - 2에서 긴 설명을 통해서 알아보았다.
최종적으로 정리해보면 본인은 Queue에서 다음과 같이 총 4개의 정보들을 관리해 주었다.
바로, 로봇이 차지하는 2개의 좌표 중, (N , N)과 상대적으로 더 가까운 좌표의 x좌표와 y좌표, 그리고 로봇의 형태를 구분하기 위해서 방향정보, 그리고 현재까지 움직인 횟수 이렇게 총 4개의 정보들을 관리해 주었다.
이 4개의 정보를 ROBOT이라는 구조체를 만들어서 관리해 주었다. 그리고 중복탐색에 대한 처리는 Visit배열을 만들어서 관리해 주었다.
struct ROBOT
{
int x;
int y;
int Dir;
int Cnt;
};
bool Visit[110][110][4];Visit배열의 가장 마지막에 4칸을 차지하고 있는 인덱스가 의미하는 바는 "동서남북" 이다.
#2. BFS탐색
위와 같은 정보들을 알았으니, 실제로 탐색을 할 때에는 어떻게 진행되는지 조금 구체적으로 알아보자.
가장 초기 상태는 어떻게 될까 ?? 가장 초기에 Queue에 들어가는 정보는 뭐가 될까 ???
가장 초기에 로봇은 (0 , 0)과 (0 , 1)을 차지하는 가로로 긴 형태로 존재하게 될 것이다.
그렇다면 이 중, 우리가 골라야 할 기준이 되는 좌표는 뭐가 될까 ?? 바로 (0 , 1)이다. 왜 ? 상대적으로 (N , N)에 더 가깝기 때문이다. 그렇다면 가장 초기의 방향정보는 어떻게 될까 ?? (0 , 1)을 기준으로 나머지 로봇이 (0 , 0)에 존재하게 된다. 즉 ! 방향은 서쪽방향이 될 것이다. 당연히 현재까지 움직인 횟수는 0번일 것이다.
그럼, 가장 초기에 방문표시는 어떻게 해줄까 ?? 중복방지를 위한 방문표시는 2개의 좌표 모두 해주어야 한다.
기준이 되는 좌표만 해주어서는 안된다.
그럼 어떻게 될까 ?? 첫 번째로 "(0 , 1)에서 서쪽에 로봇이 존재하는 형태는 이미 방문했습니다" 가 될 것이다.
두 번째로 "(0 , 0)에서 오른쪽에 로봇이 존재하는 형태는 이미 방문했습니다" 가 될 것이다.
즉 ! Visit[0][1][1] = true & Visit[0][0][0] = true 로 표현할 수 있다.
※ 본인이 설정한 방향정보는 동서남북 순서대로 0,1,2,3 입니다 ※
그럼 지금부터 로봇이 회전하는 것이 아닌 단순히 상하좌우로 움직이는 것을 알아볼 것인데, 로봇이 가로의 형태로 있던, 세로의 형태로 있던 몇 가지 공통적으로 작용되는 부분이 있어서 한번에 알아보도록 하자.
#2 - 1) 기준점이 아니었던 좌표가 기준점이 되는 움직임
먼저 제목의 말을 이해해보자. 기준점이 아니었던 좌표라는 것은, 움직이기 전에는 옆에 있는 좌표보다 상대적으로 (N , N)과 거리가 더 멀어서 기준점이 되지 않았던 좌표들이지만, 한번의 움직임을 통해서 이 좌표들이 기준점이 되는 경우이다.
과연 이게 어느 경우일까 ??? 다음과 같은 2가지 상황을 한번 보자.
위의 그림 A와 B를 보자.
먼저 각 그림들의 왼쪽 그림들이 기존의 상태를 나타내고, 오른쪽 그림들이 한번 움직인 후의 상태를 나타낸다.
그리고 각 그림들에 있는 초록색 별이 위치한 좌표들에 대해서 잘 살펴보자.
먼저, 그림 A에서 초록색 별이 있는 좌표는 기준점으로 선택되지 못한 좌표이다. 왜냐하면 옆에 연결되어 있는 로봇의 좌표가 상대적으로 (N , N)에 더 가깝기 떄문에 기준점으로 선택되지 못한 것이다.
그런데 ! 이 때, 이 로봇이 왼쪽으로 한 칸 움직이게 된다면 초록색별이 있는 좌표는 기준점으로 바뀌게 된다.
그림 B도 마찬가지이다. 첫 번째 그림에 있는 별이 있는 좌표는 기준점으로 선택되지 못한 좌표인데, 이 때 로봇이 위쪽으로 한칸 움직이게 된다면 초록색별이 있는 좌표는 기준점으로 바뀌게 된다.
그렇다면 로봇이 어느 방향으로 있던지 상관없이 어떤 경우에 "기준점이 아니었던 좌표가 기준점이 될까 ?"
바로 ! 우리가 관리하고 있는 "방향"과 동일한 방향으로 움직이게 될 경우 기준점이 아니었던 좌표가 기준점이 된다.
그림 A의 첫번째 그림부터 확인해보자.
그림 A의 첫 번째 그림에서 기준점이 되는 좌표를 (x , y)라고 가정해보자. 그리고 현재 로봇의 방향은 서쪽이 된다.
왜냐하면 기준점이 되는 좌표에서 서쪽에 로봇이 하나 더 연결되어 있으므로 로봇의 방향은 서쪽이다.
그런데 이 때 ! 서쪽으로 로봇을 한 번 움직이게 되면 ? 즉 ! 현재 로봇의 방향과 같은 방향으로 한칸 움직이게 되면 기준점이 아니었던 좌표가 기준점이 되는 것이다.
그림 B도 마찬가지이다. 그림 B의 첫 번째 그림에서 기준점이 되는 좌표를 (x , y)라고 가정해보자.
그리고 이 때 현재 로봇의 방향은 북쪽이 될 것이다. 이 상태에서 로봇을 북쪽으로 한 번 더 움직이게 되면 기준점이 아니었던 좌표가 기준점이 된다.
즉 ! "현재 로봇의 방향과 동일한 방향으로 움직이게 되면, 기준점이 아니었던 좌표가 기준점이 된다."
#2 - 2) 새로운 좌표가 기준점이 되는 움직임
새로운 좌표가 기준점이 되는 움직임은 사실 2 - 1)의 경우를 제외한 나머지 경우이다.
즉 ! 현재 설정되어 있는 방향과 같은 방향으로 움직이는 것이 아닌 경우는 모두 새로운 좌표가 새로운 기준점이 된다.
본인은 실제로 구현할 때, 현재 로봇의 방향과 반대방향으로 움직이는 경우와 그렇지 않은 경우를 이 안에서 또 나눠서 구현을 하였는데... 사실 지금보면.. 그럴 필요까지는 있었나 싶기는 하다.. 움직이려는 좌표가 빈공간인지 아닌지를 판단할 때, 이 빈공간을 1개 탐색하냐 2개 탐색하냐의 차이만 존재할 뿐이다.
조금 더 구체적으로 이야기해보면 다음과 같다.
그림 A같은 경우에는 현재 로봇이 서쪽 방향으로 존재할 때, 서쪽 방향의 반대방향인 동쪽으로 움직이는 경우를 표현한 것이다. 동쪽으로 움직이기 위해서는 파랑색 별이 있는 한 칸만 빈 공간인지 확인을 하면 된다.
하지만 반대로, 그림 B같은 경우에는 로봇이 서쪽 방향으로 존재할 때, 아래쪽으로, 즉, 남쪽으로 움직이는 경우를 표현한 것인데, 남쪽은 서쪽의 반대방향이 아니기 때문에 남쪽에 있는 2칸을 모두 빈공간인지 확인을 해주어야 한다.
이렇게 몇 칸을 비교하는지에 따라서 나누기 위해서, "현재 로봇의 방향의 반대방향으로 움직이는 경우와 그렇지 않은 경우" 로 또 나눠서 구현을 하였다.
회전을 하기에 앞서 위와 같이 단순히 상하좌우로 움직이는 과정을 나타내 보았다.
물론! 이 과정에서 방문처리도 해주어야 하는데.. 방문처리 같은 경우에는 별도의 설명을 하지는 않겠다.
위에서도 이야기했듯이, 방문처리는 기준점이 되는 좌표 뿐만 아니라 기준점이 아닌 좌표에 대해서도 계속 해주어야 하고, 로봇이 움직이는 것에 따라서 어떤 좌표의 어떤 방향에 로봇이 있는지를 생각하면서 직접 구현해 보도록 하자.
지금까지의 코드를 확인하고 회전하는 단계로 넘어가보자.
/* 초기화. */
/* 동쪽 = 0 , 서쪽 = 1 , 남쪽 = 2 , 북쪽 = 3 */
queue<ROBOT> Q;
Q.push({ 0, 1, 1, 0 });
Visit[0][0][0] = Visit[0][1][1] = true;
while (Q.empty() == 0)
{
int x = Q.front().x;
int y = Q.front().y;
int Dir = Q.front().Dir;
int Cnt = Q.front().Cnt;
int xx = x + dx[Dir];
int yy = y + dy[Dir];
Q.pop();
if ((x == N - 1 && y == N - 1) || (xx == N - 1 && yy == N - 1)) return Cnt;
for (int i = 0; i < 4; i++)
{
/* 기준점이 아니었던 좌표가 기준점이 되는 경우. */
/* 현재 로봇의 방향과 같은 방향으로 움직일 경우 위와 같은 상황이 발생. */
if (i == Dir)
{
int nx = xx + dx[i];
int ny = yy + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (board[nx][ny] == 0 && Visit[nx][ny][Reverse(Dir)] == false && Visit[xx][yy][Dir] == false)
{
Visit[x][y][Reverse(Dir)] = true;
Visit[xx][yy][Dir] = true;
Q.push({ xx, yy, Dir, Cnt + 1 });
}
}
}
/* 새로운 좌표가 기준점이 되는 경우. */
/* 현재 로봇의 방향과 반대 방향으로 움직일 경우 한 칸의 좌표만 확인. */
/* 그게 아닌 방향에 대해서는 2개의 좌표 모두 확인. */
else if(i == Reverse(Dir))
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (board[nx][ny] == 0 && Visit[nx][ny][Dir] == false && Visit[x][y][Reverse(Dir)] == false)
{
Visit[nx][ny][Dir] = true;
Visit[x][y][Reverse(Dir)] = true;
Q.push({ nx, ny, Dir, Cnt + 1 });
}
}
}
else
{
int nx = x + dx[i];
int ny = y + dy[i];
int nxx = xx + dx[i];
int nyy = yy + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N && nxx >= 0 && nyy >= 0 && nxx < N && nyy < N)
{
if (board[nx][ny] == 0 && board[nxx][nyy] == 0)
{
if (Visit[nx][ny][Dir] == false && Visit[nxx][nyy][Reverse(Dir)] == false)
{
Visit[nx][ny][Dir] = true;
Visit[nxx][nyy][Reverse(Dir)] = true;
Q.push({ nx, ny, Dir, Cnt + 1 });
}
}
}
}
}
#2 - 3) 회전하기
먼저 로봇이 가로로 긴 형태로 존재할 때를 알아보자.
먼저 그림 A를 한번 살펴보자. A의 첫 번째 그림처럼 로봇이 존재할 때, 로봇을 위쪽으로 회전시킨다면 A의 2번, 3번 그림처럼 결과가 나올 것이다. 그런데 ! 2번처럼 회전을 시키든, 3번처럼 회전을 시키든 공통적인 부분이 하나 있다.
바로, 1번 그림에서 별표친 좌표들이 빈 공간이여야 한다는 것이다.
그림 B는 첫 번째 그림처럼 로봇이 존재할 때, 아래쪽으로 로봇을 회전시키는 것을 2번 3번 그림으로 나타낸 것인데, 이도 마찬가지로 몇 번 그림으로 만들기 위해서든 별표친 아래의 2개의 좌표가 모두 빈공간 이여야 한다는 것이다.
이 부분만 잘 체크를 해주면 된다.
세로로 긴 형태도 마찬가지이다. 세로로 긴 형태의 그림을 가로로 만들기 위해서는 각각 양쪽에 있는 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
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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct ROBOT
{
int x;
int y;
int Dir;
int Cnt;
};
int N;
bool Visit[110][110][4];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int Reverse(int Dir)
{
if (Dir == 0) return 1;
else if (Dir == 1) return 0;
else if (Dir == 2) return 3;
else if (Dir == 3) return 2;
}
int BFS(vector<vector<int>> board)
{
queue<ROBOT> Q;
Q.push({ 0, 1, 1, 0 });
Visit[0][0][0] = Visit[0][1][1] = true;
while (Q.empty() == 0)
{
int x = Q.front().x;
int y = Q.front().y;
int Dir = Q.front().Dir;
int Cnt = Q.front().Cnt;
int xx = x + dx[Dir];
int yy = y + dy[Dir];
Q.pop();
if ((x == N - 1 && y == N - 1) || (xx == N - 1 && yy == N - 1)) return Cnt;
for (int i = 0; i < 4; i++)
{
if (i == Dir)
{
int nx = xx + dx[i];
int ny = yy + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (board[nx][ny] == 0 && Visit[nx][ny][Reverse(Dir)] == false && Visit[xx][yy][Dir] == false)
{
Visit[x][y][Reverse(Dir)] = true;
Visit[xx][yy][Dir] = true;
Q.push({ xx, yy, Dir, Cnt + 1 });
}
}
}
else if(i == Reverse(Dir))
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N)
{
if (board[nx][ny] == 0 && Visit[nx][ny][Dir] == false && Visit[x][y][Reverse(Dir)] == false)
{
Visit[nx][ny][Dir] = true;
Visit[x][y][Reverse(Dir)] = true;
Q.push({ nx, ny, Dir, Cnt + 1 });
}
}
}
else
{
int nx = x + dx[i];
int ny = y + dy[i];
int nxx = xx + dx[i];
int nyy = yy + dy[i];
if (nx >= 0 && ny >= 0 && nx < N && ny < N && nxx >= 0 && nyy >= 0 && nxx < N && nyy < N)
{
if (board[nx][ny] == 0 && board[nxx][nyy] == 0)
{
if (Visit[nx][ny][Dir] == false && Visit[nxx][nyy][Reverse(Dir)] == false)
{
Visit[nx][ny][Dir] = true;
Visit[nxx][nyy][Reverse(Dir)] = true;
Q.push({ nx, ny, Dir, Cnt + 1 });
}
}
}
}
}
if (Dir == 0 || Dir == 1)
{
int cx = x - 1;
int cxx = xx - 1;
if (cx >= 0 && cxx >= 0 && cx < N && cxx < N)
{
if (board[cx][y] == 0 && board[cxx][yy] == 0)
{
if (Visit[x][y][3] == false && Visit[cx][y][2] == false)
{
Visit[x][y][3] = true;
Visit[cx][y][2] = true;
Q.push({ x, y, 3, Cnt + 1 });
}
if (Visit[cxx][yy][2] == false && Visit[xx][yy][3] == false)
{
Visit[cxx][yy][2] = true;
Visit[xx][yy][3] = true;
Q.push({ cxx, yy, 2, Cnt + 1 });
}
}
}
cx = x + 1;
cxx = xx + 1;
if (cx >= 0 && cxx >= 0 && cx < N && cxx < N)
{
if (board[cx][y] == 0 && board[cxx][yy] == 0)
{
if (Visit[x][y][2] == false && Visit[cx][y][3] == false)
{
Visit[x][y][2] = true;
Visit[cx][y][3] = true;
Q.push({ x, y, 2, Cnt + 1 });
}
if (Visit[cxx][yy][3] == false && Visit[xx][yy][2] == false)
{
Visit[cxx][yy][3] = true;
Visit[xx][yy][2] = true;
Q.push({ cxx, yy, 3, Cnt + 1 });
}
}
}
}
else
{
int cy = y - 1;
int cyy = yy - 1;
if (cy >= 0 && cyy >= 0 && cy < N && cyy < N)
{
if (board[x][cy] == 0 && board[xx][cyy] == 0)
{
if (Visit[x][y][1] == false && Visit[x][cy][0] == false)
{
Visit[x][y][1] = true;
Visit[x][cy][0] = true;
Q.push({ x, y, 1, Cnt + 1 });
}
if (Visit[xx][yy][1] == false && Visit[xx][cyy][0] == false)
{
Visit[xx][yy][1] = true;
Visit[xx][cyy][0] = true;
Q.push({ xx, cyy, 0, Cnt + 1 });
}
}
}
cy = y + 1;
cyy = yy + 1;
if (cy >= 0 && cyy >= 0 && cy < N && cyy < N)
{
if (board[x][cy] == 0 && board[xx][cyy] == 0)
{
if (Visit[x][y][0] == false && Visit[x][cy][1] == false)
{
Visit[x][y][0] = true;
Visit[x][cy][1] = true;
Q.push({ x, y, 0, Cnt + 1 });
}
if (Visit[xx][yy][0] == false && Visit[xx][cyy][1] == false)
{
Visit[xx][yy][0] = true;
Visit[xx][cyy][1] = true;
Q.push({ xx, cyy, 1, Cnt + 1 });
}
}
}
}
}
return 0;
}
int solution(vector<vector<int>> board)
{
N = board.size();
int answer = BFS(board);
return answer;
}
|
cs |
'[ Programmers Code ] > # PG - Level3' 카테고리의 다른 글
| [ 프로그래머스 경주로 건설 (Lv3) ] (C++) (4) | 2021.03.21 |
|---|---|
| [ 프로그래머스 징검다리 건너기 (Lv3) ] (C++) (0) | 2021.03.17 |
| [ 프로그래머스 카드 짝 맞추기 (Lv3) ] (C++) (0) | 2021.02.03 |
| [ 프로그래머스 광고 삽입 (Lv3) ] (C++) (7) | 2021.02.03 |
| [ 프로그래머스 합승 택시 요금 (Lv3) ] (C++) (2) | 2021.02.02 |