본문 바로가기
삼성 코팅테스트 준비/모의 역량 테스트 문제

1953 탈주범 검거

by tryotto 2020. 3. 4.

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <utility>
 
using namespace std;
 
int height, width;
int st_x, st_y;
int time_len;
int pipe[60][60];
queue<pair<pair<int, int>, int> > q;    //((y,x), time)
 
void initialize();
void bfs();
int count();
int match(int move, int dir);
 
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        initialize();
 
        bfs();
 
        printf("#%d %d\n", t, count());
    }
}
 
void bfs() {
    q.push(make_pair(make_pair(st_y, st_x), 1));
 
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int time = q.front().second;
        q.pop();
 
        if (time > time_len)
            break;
 
        int dir = pipe[y][x];
 
        pipe[y][x] = -1;
 
        switch (dir) {
        case 1:    //up, down, left, right
            if ((y - 1 >= 1) && (pipe[y - 1][x] > 0) && (match(1, pipe[y - 1][x])))
                q.push(make_pair(make_pair(y - 1, x), time + 1));
            if ((y + 1 <= height) && (pipe[y + 1][x] > 0) && (match(2, pipe[y + 1][x])))
                q.push(make_pair(make_pair(y + 1, x), time + 1));
            if ((x - 1 >= 1) && (pipe[y][x - 1] > 0) && (match(3, pipe[y][x-1])))
                q.push(make_pair(make_pair(y, x - 1), time + 1));
            if ((x + 1 <= width) && (pipe[y][x + 1] > 0) && (match(4, pipe[y][x + 1])))
                q.push(make_pair(make_pair(y, x + 1), time + 1));
            break;
        case 2://up, down
            if ((y - 1 >= 1) && (pipe[y - 1][x] > 0) && (match(1, pipe[y - 1][x])))
                q.push(make_pair(make_pair(y - 1, x), time + 1));
            if ((y + 1 <= height) && (pipe[y + 1][x] > 0) && (match(2, pipe[y + 1][x])))
                q.push(make_pair(make_pair(y + 1, x), time + 1));
            break;
        case 3://left, right
            if ((x - 1 >= 1) && (pipe[y][x - 1] > 0) && (match(3, pipe[y][x - 1])))
                q.push(make_pair(make_pair(y, x - 1), time + 1));
            if ((x + 1 <= width) && (pipe[y][x + 1] > 0) && (match(4, pipe[y][x + 1])))
                q.push(make_pair(make_pair(y, x + 1), time + 1));
            break;
        case 4://up, right
            if ((y - 1 >= 1) && (pipe[y - 1][x] > 0) && (match(1, pipe[y - 1][x])))
                q.push(make_pair(make_pair(y - 1, x), time + 1));
            if ((x + 1 <= width) && (pipe[y][x + 1] > 0) && (match(4, pipe[y][x + 1])))
                q.push(make_pair(make_pair(y, x + 1), time + 1));
            break;
        case 5://down, right
            if ((y + 1 <= height) && (pipe[y + 1][x] > 0) && (match(2, pipe[y + 1][x])))
                q.push(make_pair(make_pair(y + 1, x), time + 1));
            if ((x + 1 <= width) && (pipe[y][x + 1] > 0) && (match(4, pipe[y][x + 1])))
                q.push(make_pair(make_pair(y, x + 1), time + 1));
            break;
        case 6://down, left
            if ((y + 1 <= height) && (pipe[y + 1][x] > 0) && (match(2, pipe[y + 1][x])))
                q.push(make_pair(make_pair(y + 1, x), time + 1));
            if ((x - 1 >= 1) && (pipe[y][x - 1] > 0) && (match(3, pipe[y][x - 1])))
                q.push(make_pair(make_pair(y, x - 1), time + 1));
            break;
        case 7://up, left
            if ((y - 1 >= 1) && (pipe[y - 1][x] > 0) && (match(1, pipe[y - 1][x])))
                q.push(make_pair(make_pair(y - 1, x), time + 1));
            if ((x - 1 >= 1) && (pipe[y][x - 1] > 0) && (match(3, pipe[y][x - 1])))
                q.push(make_pair(make_pair(y, x - 1), time + 1));
            break;
        }
    }
}
 
int count() {
    int cnt = 0;
    for (int i = 1; i <= height; i++)
        for (int j = 1; j <= width; j++)
            if (pipe[i][j] == -1)
                cnt++;
 
    return cnt;
}
 
// move- 1:상 2:하 3:좌 4:우
int match(int move, int dir) {
    switch (move) {
    case 1:
        if ((dir == 1) || (dir == 2) || (dir == 5) || (dir == 6))
            return 1;
        break;
    case 2:
        if ((dir == 1) || (dir == 2) || (dir == 4) || (dir == 7))
            return 1;
        break;
    case 3:
        if ((dir == 1) || (dir == 3) || (dir == 4) || (dir == 5))
            return 1;
        break;
    case 4:
        if ((dir == 1) || (dir == 3) || (dir == 6) || (dir == 7))
            return 1;
        break;
    }
    return 0;
}
 
void initialize() {
    // queue
    while (!q.empty())
        q.pop();
 
    // scanf
    scanf("%d %d %d %d %d", &height, &width, &st_y, &st_x, &time_len);
    st_x += 1;
    st_y += 1;
 
    // memset
    memset(pipe, 0, sizeof(pipe));
 
    // for 문
    for (int i = 1; i <= height; i++)
        for (int j = 1; j <= width; j++)
            scanf("%d", &pipe[i][j]);
}
 
 
cs


로직이 아주 단순했던 bfs 문제였다

세밀한 검산이 별로 필요 없었다.



저작자표시

'삼성 코팅테스트 준비 > 모의 역량 테스트 문제' 카테고리의 다른 글

2117 홈 방범 서비스  (0) 2020.03.05
4014 활주로 건설  (0) 2020.03.04
2477 차량 정비소  (0) 2020.03.04
2105 디저트 카페  (0) 2020.03.03
2115 벌꿀채취  (0) 2020.03.03

관련글

티스토리툴바