Backjoon Online Judge
"2178번 : 미로탐색" 문제입니다.
문제 링크 : https://www.acmicpc.net/problem/2178
'2178번 : 미로탐색' 문제의 경우 BFS로 문제를 해결했습니다.
이전에 풀었던 '7576번 : 토마토' 문제의 코드를 살짝 변경하여 해결했습니다.
(참고링크 : http://rehu.tistory.com/20)
문제 및 코드 설명입니다.
먼저 미로의 상태를 저장하기 위해 2차원 배열로 미로를 저장했습니다.
이때 BFS를 쉽게 구현하기 위해 큐를 pair로 선언하여 x좌표, y좌표를 저장했습니다.
또 미로의 상태를 연속된 숫자로 입력받으므로 일반적인 입력으로는 미로에 숫자를 하나씩 저장할 수 없습니다.
char형 배열을 통해 문자로 입력받고 ASCII 변환을 이용하여 숫자를 배열에 하나씩 저장했습니다.
이후 시작점에서부터 상하좌우에 길이 있는지 확인하고 길이 있다면 이동횟수를 길에 저장하도록 했습니다.
(시작점의 경우 1로 설정하면 한칸 이동했다가 다시 시작점 방향으로 탐색하기 때문에 0으로 초기화 했습니다.
물론 시작점 방향으로 탐색하면 곧 탐색이 종료되기에 초기화 과정 없이도 정답이 나오긴 합니다.)
미로의 시작점과 끝 점은 가장 멀리 있으므로 큐의 모든 원소가 사라질때까지 반복했으며, BFS 탐색 후 도착점의 값을 출력해 주었습니다.
코드는 C++로 작성하였습니다.
(단, 큐를 pair을 이용해 구현하여 C++ 11 이상에서만 정상작동 합니다.
C++ 11 이하에서 작동되기를 원하시면 큐를 pair로 구현하는 대신 2개를 만들면 됩니다.)
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 | #include <iostream> #include <queue> #define Max 100 using namespace std; int main() { int M, N, x, y, tx, ty; char tmp[Max]; int maze[Max][Max] = { 0, }; int result = 0; queue<pair<int, int>> q; cin >> N >> M; for (int i = 0; i < N; i++) { cin >> tmp; for (int j = 0; j < M; j++) { maze[i][j] = tmp[j] - 48; } } maze[0][0] = 0; q.push(make_pair(0, 0)); int side[4] = { 1, 0, -1, 0 }; while (!q.empty()) { x = q.front().first; y = q.front().second; if (maze[x][y] == 2 + result) result++; for (int i = 0; i < 4; i++) { tx = x - side[i]; ty = y - side[3 - i]; if (0 <= tx && tx < N && 0 <= ty && ty < M) { if (maze[tx][ty] == 1) { maze[tx][ty] = 2 + result; q.push(make_pair(tx, ty)); } } } q.pop(); } cout << maze[N-1][M-1] << endl; cin >> N; } |
'Programming 문제풀이 > Backjoon Online Judge' 카테고리의 다른 글
| 2667번 : 단지번호붙이기 (0) | 2018.05.29 |
|---|---|
| 2606번 : 바이러스 (0) | 2018.05.28 |
| 7569번 : 토마토 (0) | 2018.05.17 |
| 7576번 : 토마토 (0) | 2018.05.16 |
| 2293번 : 동전 1 (0) | 2018.05.15 |