SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
www.swexpertacademy.com
시작점을 큐에 넣고 bfs를 사용해서 도착점에 방문하는지 확인해주면 된다.
도착점을 확인하기 위해 입력받을 때 도착점의 좌표를 따로 저장해둔다.
bfs를 할 때 길인 경우(값이 0인 경우)에만 방문을 하게 해서 계속 답이 0이 나왔었다...ㅠㅠ
도착지점인 경우(값이 3인 경우)도 방문하도록 해줘야 한다!
결과적으로 도착지점에 방문을 했으면 1을 출력 못했으면 0을 출력하면 된다.
참고로 미로2 문제도 미로의 크기만 100으로 하면 똑같이 풀 수 있다.
|
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
|
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int map[16][16];
bool check[16][16];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
int T = 10;
int num;
for(int tc=1; tc<=T; tc++) {
scanf("%d",&num);
int endX, endY;
queue<pair<int,int> > q;
for(int i=0; i<16; i++) {
for(int j=0; j<16; j++) {
scanf("%1d", &map[i][j]);
check[i][j] = false;
//시작점이면 큐에 삽입후 방문 체크
if(map[i][j] == 2) {
q.push(make_pair(i,j));
check[i][j] = true;
} else if(map[i][j] == 3) { //도착점의 좌표를 저장
endX = i;
endY = j;
}
}
}
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
//범위 체크
if(nx < 0 || ny < 0 || nx >= 100 || ny >= 100) continue;
//길이고, 방문하지 않았으면 방문
if(map[nx][ny] == 0 && check[nx][ny] == false) {
q.push(make_pair(nx,ny));
check[nx][ny] = true;
} else if(map[nx][ny] == 3) {
//도착점인 경우 방문
q.push(make_pair(nx,ny));
check[nx][ny] = true;
}
}
}
//도착점에 방문했으면 1을 출력
if(check[endX][endY]) {
printf("#%d %d\n",tc,1);
} else { //도착점에 도착하지 못했으면 0을 출력
printf("#%d %d\n",tc,0);
}
}
return 0;
}
Colored by Color Scripter
|
'SWEA > D4' 카테고리의 다른 글
| [SWEA] 9282. 초콜릿과 건포도 (0) | 2020.03.04 |
|---|---|
| [SWEA] 1486. 장훈이의 높은 선반 (0) | 2019.06.27 |
| [SWEA] 7829. 보물왕 태혁 (0) | 2019.06.27 |
