728x90
반응형
https://www.acmicpc.net/problem/1938
1938번: 통나무 옮기기
첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4<=N<=50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문자 사이에는 빈칸이 없다. 통나무와 최종 위치의 개수는 1개이다.
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
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
|
#include<stdio.h>
#include<vector>
#include<queue>
#define NSIZE 51
using namespace std;
char input[NSIZE][NSIZE];
int chk[NSIZE][NSIZE][2];
int N;
int dy[] = { -1,1,0,0,0 };
int dx[] = { 0,0,-1,1,0 };
struct Tree {
int y, x, cnt, dir;
};
vector<Tree>T;
queue<Tree> q;
int ret = 0x7fffffff;
void init()
{
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%s", input[i]);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (input[i][j] == 'B') {
T.push_back({ i,j,0,0 });
}
}
}
if (input[T[1].y - 1][T[1].x] == 'B' && input[T[1].y][T[1].x] == 'B' && input[T[1].y + 1][T[1].x] == 'B') {
// 수직인 경우
input[T[1].y - 1][T[1].x] = '0'; input[T[1].y][T[1].x] = '0'; input[T[1].y + 1][T[1].x] = '0';
q.push({ T[1].y,T[1].x,0,0 });
chk[T[1].y][T[1].x][0] = 1;
}
if (input[T[1].y][T[1].x-1] == 'B' && input[T[1].y][T[1].x] == 'B' && input[T[1].y][T[1].x+1] == 'B') {
// 수직인 경우
input[T[1].y][T[1].x - 1] = '0'; input[T[1].y][T[1].x] = '0'; input[T[1].y][T[1].x + 1] = '0';
q.push({ T[1].y,T[1].x,0,1 });
chk[T[1].y][T[1].x][1] = 1;
}
}
void bfs() {
while (!q.empty()) {
Tree c = q.front(); q.pop();
if (c.dir == 0) {
if (input[c.y - 1][c.x] == 'E' && input[c.y][c.x] == 'E' && input[c.y + 1][c.x] == 'E')
{
ret = c.cnt;
return;
}
}
else {
if (input[c.y][c.x - 1] == 'E' && input[c.y][c.x] == 'E' && input[c.y][c.x + 1] == 'E')
{
ret = c.cnt;
return;
}
}
for (int dir = 0; dir < 5; dir++) {
Tree n = c;
n.cnt++;
if (dir == 4) {// 회전 T 명령
if (0 <= n.y - 1 && n.y - 1 < N && 0 <= n.x - 1 && n.x - 1 < N &&
0 <= n.x && n.x < N && 0 <= n.x + 1 && n.x + 1 < N && 0 <= n.y && n.y < N &&
0 <= n.y + 1 && n.y + 1 < N) {
if (n.dir == 0) {// 수직인경우
if (chk[n.y][n.x][1] == 0 && input[n.y - 1][n.x - 1] != '1' && input[n.y - 1][n.x] != '1' &&
input[n.y - 1][n.x + 1] != '1' && input[n.y][n.x + 1] != '1' && input[n.y + 1][n.x + 1] != '1' &&
input[n.y + 1][n.x] != '1' && input[n.y + 1][n.x - 1] != '1' && input[n.y][n.x - 1] != '1') {
chk[n.y][n.x][1] = 1;
n.dir = 1;
q.push(n);
}
}
else {// 수평인경우
if (chk[n.y][n.x][0] ==0 && input[n.y - 1][n.x - 1] != '1' && input[n.y - 1][n.x] != '1' &&
input[n.y - 1][n.x + 1] != '1' && input[n.y][n.x + 1] != '1' && input[n.y + 1][n.x + 1] != '1' &&
input[n.y + 1][n.x] != '1' && input[n.y + 1][n.x - 1] != '1' && input[n.y][n.x - 1] != '1') {
chk[n.y][n.x][0] = 1;
n.dir = 0;
q.push(n);
}
}
}
}
else { // 위 아래 왼쪽 오른쪽 경우
n.y += dy[dir];
n.x += dx[dir];
if (n.dir == 0) {// 수직
if (0<=n.x&&n.x<N&&0 <= n.y && n.y < N && 0 <= n.y - 1 && n.y - 1 < N && 0 <= n.y + 1 && n.y + 1 < N ) {
if (chk[n.y][n.x][0] == 0 && input[n.y - 1][n.x] != '1' && input[n.y][n.x] != '1' && input[n.y + 1][n.x] != '1') {
chk[n.y][n.x][0] = 1;
q.push(n);
}
}
}
else {// 수평
if (0<=n.y&&n.y<N&&0 <= n.x && n.x < N && 0 <= n.x - 1 && n.x - 1 < N && 0 <= n.x + 1 && n.x + 1 < N) {
if (chk[n.y][n.x][1] == 0 && input[n.y][n.x - 1] != '1' && input[n.y][n.x] != '1' && input[n.y][n.x + 1] != '1') {
chk[n.y][n.x][1] = 1;
q.push(n);
}
}
}
}
}
}
}
int main(void) {
init();
bfs();
if (ret == 0x7fffffff) {
ret = 0;
}
printf("%d\n", ret);
return 0;
}
|
문제를 다 풀고 나서 검사를 해보았는데 틀렸다고 했습니다. 그래서 어떤것이 틀렸는지 봤는데 회전시키는경우에
실수로 괄호를 잘못묶어서 수직인경우는 들어가는데 수평인 경우가 들어가지 않아 문제가 생겼습니다.
정말 이런 실수 옳지않죠? 여러분은 실수 하지마세요 정말 정신에 해롭습니다.
이번 문제는 좀 소스가 길긴하지만 포인트를 말씀드리면
통나무에서 가운데의 통나무를 가지고 이동을 시키되 , 양쪽의 통나무를 체크 용도로만 해주면 된다는것입니다.
대신 이경우에는 수직인경우와 수평인 경우가 있기때문에 3차원 배열을 사용하여 수평인경우 수직인 경우를 체크하기 위함입니다.
1, 1 이 중심이면 회전시 양방향에 1이 없어야하며
수직인 경우 , 수평인 경우를 잘 체크하시면 문제는 수월하게 풀립니다. 하지만 소스가 길어지네요 ㅜ
오늘은 여기까지이고 여러분들도 파팅하세요
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 1726 로봇 (0) | 2019.09.17 |
|---|---|
| 백준 2468 안전영역 (0) | 2019.09.17 |
| 백준 3987 보이저 1호 (0) | 2019.09.09 |
| 백준 2174 로봇 시뮬레이션 (0) | 2019.09.09 |
| 백준 2529 부등호 (0) | 2019.09.09 |
댓글