문제 출처 : SW Expert
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
www.swexpertacademy.com
Q. 출발지와 도착지가 주어졌을 때, 출발지 부터 도착지 까지 경로가 있는 지 판단하는 프로그램을 작성하시오.
단, 지도는 100X100 행렬 형태이며, 출발지는 2, 도착지는 3, 경로는 0, 벽은 1로 표현된다.
전형적인 완전탐색 문제에요. 탐색을 진행하다 도착지에 도달하면 탐색을 끝내는 방향으로 문제를 해결했습니다.
bfs로도 해결할 수 있지만 저는 dfs로 해결했습니다.
너무 기본적인 해결방법이라 더 이상의 설명보다 코드를 보여드리는게 나을 꺼 같습니다. 헤헤
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
|
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int map[102][102];
int check[102][102];
int dir_x[4] = { 0,1,0,-1 };
int dir_y[4] = { 1,0,-1,0 };
int result = 0;
void dfs(int x, int y) {
int chance = 0;
check[y][x] = 1; // 중복 탐색 방지
for (int i = 0; i < 4; i++) {
int next_x = x + dir_x[i];
int next_y = y + dir_y[i];
if (map[next_y][next_x] == 3) {
result = 1;
}
else if (map[next_y][next_x] == 0 && check[next_y][next_x] == 0 && result == 0) { // result를 검사, 도착지에 방문하면 탐색 종료
dfs(next_x, next_y);
}
}
}
int main() {
int T = 10;
int idx = 0;
while (idx++ < T) {
int n;
cin >> n;
memset(map, -1, sizeof(map));
string s;
int start_x = 0;
int start_y = 0;
for (int i = 1; i < 101; i++) {
cin >> s;
for (int j = 1; j < 101; j++) {
map[i][j] = s[j - 1] - '0';
if (map[i][j] == 2) {
start_y = i;
start_x = j;
}
}
}
dfs(start_x, start_y);
if (result == 1)
cout << "#" << idx << " 1" << endl;
else
cout << "#" << idx << " 0" << endl;
result = 0;
memset(check, 0, sizeof(check));
}
}
cs
|
의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!
'전체 > 알고리즘 문제풀이' 카테고리의 다른 글
백준 15684. 사다리 조작 (0) | 2019.04.11 |
---|---|
SW Expert 1232. [S/W 문제해결 기본] 9일차 - 사칙연산(D4) (0) | 2019.04.04 |
후위연산식으로 변환 (0) | 2019.04.02 |
SW Expert 1224. [S/W 문제해결 기본] 6일차 - 계산기3(D4) (0) | 2019.04.02 |
SW Expert 1223. [S/W 문제해결 기본] 6일차 - 계산기2(D4) (0) | 2019.04.02 |