SW Expert Academy 의 1226번 - 미로1 문제입니다.
16x16의 인풋으로 주어지는 미로 데이터에서 도착점까지 갈 수 있는지 여부를 판단해 출력합니다.
- 난이도 : 3
문제 조건
- 총 10개의 테스트 케이스가 주어진다.
- 한 개의 테스트 케이스 당, 16x16 의 행렬 값을 인풋으로 받는다.
- 다음은 그 인풋값을 그림으로 나타낸 결과이다.
- 위 그림과 같이 2 에서 시작하여 3으로 갈 수 있는 경로가 있는지 탐색해야 한다.
- 0은 갈 수 있는 길, 1은 갈 수 없는 벽이다.
Input
첫 줄에는 테스트 케이스 번호, 그 다음 줄에는 16x16 미로 데이터가 주어진다.
Output
2에서 3까지 갈 수 있는 경로가 존재하면 1, 없으면 0을 출력한다.
생각한 아이디어
우선 16x16 데이터를 2차원 배열에 담은 뒤, 시작 위치를 행, 열 번호값으로 담아두었습니다.
그런 다음 왼쪽, 오른쪽, 위, 아래 중 갈 수 있는 방향(즉, 0이 있는 곳)으로 위치를 옮기되,
이미 방문한 곳으로는 다시 가지 않도록, 이동하기 전의 현재 위치에는 8 이라고 데이터를 입력해 놓았습니다.
또한 길을 따라 가다가 벽에 막혀서 되돌아와야 할 경우를 대비하여,
지나온 길들의 좌표를 stack 자료구조에 저장하기로 했습니다.
이 때 좌표쌍은 C++의 STL에서 데이터 쌍을 표현할 때 사용하는 pair 클래스를 사용했습니다.
stack은 가장 최근에 넣은 것이 제일 위에 있으므로, 꺼낼 때도 그 최신 데이터가 꺼내집니다.
반면 queue는 가장 최근에 넣은 것이 맨 뒤로 가고, 꺼내는 데이터는 가장 오래된 것입니다.
그러므로 여기서는 stack이 더 어울린다고 판단했습니다.
[1] 갈 수 있는 길을 찾았을 때는, 현재 위치를 스택에 저장한 뒤 다음으로 이동합니다.
(항상 방문한 위치에는 8이라고 표기한다고 생각하면 됩니다.)
[2] 벽에 막혔을 경우, 다시 되돌아가야 하므로 stack에 저장되어 있던 데이터들을 활용합니다. 스택의 top에 저장되어 있던 좌표로 되돌아가며, top에 있는 데이터는 pop합니다.
[3] 지나온 경로를 돌아오는 와중에도 매번 상,하,좌,우를 보고 갈 수 있는 방향을 파악 중입니다.
갈 수 있는 방향을 찾았을 경우, 아까처럼 현재 위치를 stack에 push하고, 갈 수 있는 방향으로 갑니다.
[-] 만약 갈 수 있는 모든 경로를 갔는데 3을 만나지 못하고 처음 위치로 되돌아왔다면 stack은 빈 상태였을 것입니다. 이 때 미로 탐색 실패를 반환하면 됩니다.
소스코드
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
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
int main() {
int test_case;
int miro[16][16];
int s_Row, s_Col, cur_r, cur_c;
char ch;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int T = 1; T <= 10; T++) {
cin >> test_case;
cin.get(ch);
for (int row = 0; row < 16; row++) {\
for (int col = 0; col < 16; col++) {
int input = cin.get();
miro[row][col] = input - 48;
if (input - 48 == 2) {
s_Row = row; s_Col = col;
}
}
cin.get(ch);
}
// 탐색 시작
stack<pair<int, int>> s; // row,col pair를 stack에 저장
cur_r = s_Row; cur_c = s_Col;
s.push(pair<int, int>(cur_r, cur_c)); // 시작 위치를 stack에 삽입
while (1) {
miro[cur_r][cur_c] = 8;
// 오른쪽이 뚫려있을 경우
if (miro[cur_r][cur_c + 1] == 0 && s.top() != pair<int, int>(cur_r, cur_c + 1)) {
s.push(pair<int, int>(cur_r, cur_c));
cur_c = cur_c + 1;
}
// 왼쪽이 뚫려있을 경우
else if (miro[cur_r][cur_c - 1] == 0 && s.top() != pair<int, int>(cur_r, cur_c - 1)) {
s.push(pair<int, int>(cur_r, cur_c));
cur_c = cur_c - 1;
}
// 아래쪽이 뚫려있을 경우
else if (miro[cur_r + 1][cur_c] == 0 && s.top() != pair<int, int>(cur_r + 1, cur_c)) {
s.push(pair<int, int>(cur_r, cur_c));
cur_r = cur_r + 1;
}
// 위쪽이 뚫려있을 경우
else if (miro[cur_r - 1][cur_c] == 0 && s.top() != pair<int, int>(cur_r - 1, cur_c)) {
s.push(pair<int, int>(cur_r, cur_c));
cur_r = cur_r - 1;
}
else if (miro[cur_r][cur_c + 1] == 3 || miro[cur_r][cur_c-1] == 3 ||
miro[cur_r+1][cur_c] == 3 || miro[cur_r-1][cur_c] == 3) {
cout << "#" << T << " " << 1 << "\n";
break;
}
else {
cur_r = s.top().first;
cur_c = s.top().second;
s.pop();
}
if (s.empty()) {
cout << "#" << T << " " << 0 << "\n";
break;
}
}
}
}
c++의 STL에서 제공하는 stack, pair 자료구조를 이용하였습니다.
※ c++에서 cin으로 입력받기 전에, cin.tie(NULL); 을 선언하고 나서 입력받으면 실행시간이 줄어드는 효과를 얻을 수 있습니다.
※ 그러나 위와 같은 방법은 주의해서 사용하여야 한다고 합니다. 실무에서는 사용하지 말고, 싱글 쓰레드 환경에서만 사용하도록 합니다. 또한 scanf, printf와 함께 사용하면 안 됩니다. [출처 링크 : (클릭)]