728x90
반응형
https://www.acmicpc.net/problem/16509
16509번: 장군
오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 상을 어떻게 써야 할지 도와주자. 위 그림은 10×9 크기의 장기판을 나타내며, 상은 (5, 4)에, 왕은 (1, 4)에 자리 잡고 있는 기물이다. (0, 3)과 (2, 5)를 꼭짓점으로 하는 사각형과, (7, 3)과 (9, 5)를 꼭짓점으로 하는 사각형은 왕이 위치할
www.acmicpc.net
|
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
|
#include<stdio.h>
#include<queue>
#define NSIZE 10
#define MSIZE 9
using namespace std;
int input[NSIZE][MSIZE];
int chk[NSIZE][MSIZE];
int ey, ex;
int sy, sx;
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
int ddy[] = { -1,-1,1,1 };
int ddx[] = { -1,1,1,-1 };
struct Data {
int y, x, cnt;
};
void init() {
scanf("%d %d", &sy, &sx);
scanf("%d %d", &ey, &ex);
input[ey][ex] = 1;
}
void bfs() {
queue<Data>q;
q.push({ sy,sx,0 });
chk[sy][sx] = 1;
while (!q.empty()) {
Data c = q.front(); q.pop();
if (c.y==ey&&c.x==ex) {
printf("%d\n", c.cnt);
return;
}
for (int dir = 0; dir < 4; dir++) {
Data n;
n.y = c.y + dy[dir]; n.x = c.x + dx[dir]; n.cnt = c.cnt + 1;
if (n.y < 0 || n.y >= 10 || n.x < 0 || n.x >= 9)continue;
if (input[n.y][n.x] == 1)continue;
for (int cdir = 0; cdir < 2; cdir++) {
Data nn = n;
int flag = 0;
for (int cc = 0; cc < 2; cc++) {
nn.y = nn.y + ddy[(dir + cdir) % 4];
nn.x = nn.x + ddx[(dir + cdir) % 4];
if (nn.y < 0 || nn.y >= 10 || nn.x < 0 || nn.x >= 9) {
flag = 1;
break;
}
if (input[nn.y][nn.x] == 1&&cc!=1) {
flag = 1; break;
}
}
if (flag != 1) {
if (chk[nn.y][nn.x] != 1) {
chk[nn.y][nn.x] = 1;
q.push({ nn.y,nn.x,n.cnt });
}
}
}
}
}
printf("-1\n");
}
int main(void) {
init();
bfs();
return 0;
}
|
은근 문제가 처음접한다면 어려울 수 있지만 우선 기준점을 위, 아래, 왼, 오른 쪽을 기준으로 잡고 가는 위치에
장애물이 있으면 안되기때문에 기준점을 중심으로 가는 길에 장애물이 없다면 큐에 넣어주면됩니다.
dy, dx는 상하좌우 이고
ddy, ddx는 대각선을 이동시키기 위한 배열입니다.
3,3 을 중심으로 위쪽은 하늘색으로 가능 방향에 장애물만 없으면 큐에 넣기만 하면 무조건 풀리는 문제입니다.
저는 좀 복잡하게 했지만 참고 해주시면 감사하겠습니다.
그냥 기본 큐에 대각선으로 갈수 있게 경로를 다시 지정해줬다 생각하면 이해하기 쉽지 않을까요?
특이한 문제가 많아서 정말 항상 새롭네요.
오늘은 여기까지이고 다음에도 좋은 자료로 찾아 뵙겠습니다.
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 1600 말이 되고픈 원숭이 (0) | 2019.09.23 |
|---|---|
| 백준 16637 괄호 추가하기 (0) | 2019.09.22 |
| 백준 9328 열쇠 (0) | 2019.09.19 |
| 백준 6087 레이저 통신 (0) | 2019.09.19 |
| 백준 16918 봄버맨 (0) | 2019.09.17 |
댓글