티스토리 뷰
#. Problem
* The copyright in this matter is in Inflearn
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
- 미로 탈출 최단 경로의 이동한 횟수
- 격자판의 1은 벽이고, 0은 도로
- 격자판의 움직임은 상하좌우로만 움직임
- 도착할 수 없으면 '-1' 출력
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
DFS로 비슷한 문제를 풀어봤었다.
BFS로 다시 풀어보자.
BFS는 DFS와 다르게 Queue를 사용하므로 계속 탐색할 수 없다.
그러므로 탐색 과정에서의 결과를 저장해놓을 공간이 필요하다
map[]][]의 (1,1)부터 탐색하면서 도로에 왔다면 해당 도로 좌표를 Queue에 push하고 1로 수정한다. (이미 방문한 좌표이므로)
그리고 pop()한 도로로부터 이동할 수 있는 도로를 탐색한다.
이동할 수 있는 도로를 발견했다면 해당 도로의 좌표를 Queue에 push하고 마찬가지로 1로 수정한다.
그리고 이전 도로까지의 거리에서 + 1한 결과를 check[][]에 저장해두면 된다.
대략적인 과정을 그려보면 아래 그림과 같다.
이동 거리를 check[][]에 저장해주면서 종료지점에 도착했을 때,
최소 이동횟수를 result 변수에 저장해주면 되겠다.
더 자세한 과정 설명은 코드에서!
#. Code
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 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; #define MAX 2147000000 #define MIN -2147000000 int n = 7, rst = MAX, map[10][10], cnt[10][10]; int dx[4] = { -1, 0, 1, 0 }; int dy[4] = {0, 1, 0, -1 }; struct Pos { int x; int y; Pos(int a, int b) { x = a; y = b; } }; int main(void) { freopen("input.txt", "rt", stdin); int i, j, k; queue<Pos> q; fill(&map[0][0], &map[n - 1][n], 1); for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) scanf("%d", &map[i][j]); for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { if (map[i][j] == 0) { q.push(Pos(i, j)); map[i][j] = 1; while (!q.empty()) { Pos tmp = q.front(); q.pop(); for (k = 0; k < 4; k++) { int xx = tmp.x + dx[k]; int yy = tmp.y + dy[k]; if (map[xx][yy] == 0) { q.push(Pos(xx, yy)); map[xx][yy] = 1; cnt[xx][yy] = (cnt[tmp.x][tmp.y]) + 1; } if (xx == 7 && yy == 7) if (rst > cnt[xx][yy]) rst = cnt[xx][yy]; } } } } } if (rst == 0) printf("-1\n"); else printf("%d\n", rst); return 0; } | cs |
line 10~11) 상하좌우로 이동할 수 있는 좌표
line 13~22) 이번에는 좌표를 저장하는 구조체를 만들어보았다. pair와 별 다를건 없는 것 같다.
다만 좀 보기가 깔끔하다는..? (내 생각엔..)
line 30) 입력으로 주어진 좌표의 정보를 제외하고 모두 1로 초기화하였다.
테두리 좌표가 0이면 도로로 인식하고 이동해버리기 때문에..
이차원 배열 초기화를 위해 std::fill 을 사용하였다.
line 36~70) (1, 1)부터 모든 좌표를 탐색
line 40~68) 해당 좌표가 도로일 경우
line 42~43) Queue에 push해주고 이미 방문하였으므로 1로 수정
line 45~66) Queue가 다 비어질 때까지 반복
line 47~48) 현재 도로 정보를 Queue에서 빼낸다.
line 50~65) 현재 도로에서 상하좌우로 이동할 수 있는 도로가 있는지 탐색
line 52~53) 다음 도로의 좌표를 저장
line 55~60) 다음 좌표가 도로라면 좌표를 Queue에 push해주고 방문하였으므로 1로 수정
그리고 출발 지점으로부터의 거리를 cnt[][]에 저장. 출발~이전 도로까지의 거리 + 1
line 62~62) 도착 좌표에 도달하였다면 이 경로가 최솟값인지 검사하고 최솟값이라면 rst변수에 저장
line 71~74) 결과가 0이라면 도착지점에 도달하지 못 한 미로이므로 '-1' 출력
그렇지 않다면 도착 좌표인 cnt 배열의 (7,7) 원소를 출력
웃긴게 line 59에서 (cnt[tmp.x][tmp.y])++ 로 해놓고 답이 계속 제대로 안 나와서
디버깅하면서 엄청 헤맸다..ㅋㅋㅋㅋㅋ
이런 작은 실수는 실전에서 아까운 시간을 잡아먹는 요소가 되므로...
차근차근 잘 풀어나가도록 연습해야지..!
#. Other code
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 | #include <cstdio> #include <vector> #include <queue> #include <algorithm> #define x first #define y second using namespace std; int n, map[10][10], dis[10][10]; int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; struct Loc { int x; int y; Loc(int a, int b) { x = a; y = b; } }; queue<Loc> Q; int main() { freopen("input.txt", "rt", stdin); for (int i = 1; i <= 7; i++) { for (int j = 1; j <= 7; j++) { scanf("%d", &map[i][j]); } } Q.push(Loc(1, 1)); map[1][1] = 1; while (!Q.empty()) { Loc tmp = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { int xx = tmp.x + dx[i]; int yy = tmp.y + dy[i]; if (map[xx][yy] == 0 && xx >= 1 && xx <= 7 && yy >= 1 && yy <= 7) { Q.push(Loc(xx, yy)); map[xx][yy] = 1; dis[xx][yy] = dis[tmp.x][tmp.y] + 1; } } } if (dis[7][7] == 0) printf("-1\n"); else printf("%d\n", dis[7][7]); return 0; } | cs |
강사님의 코드를 보고나니.. 나는 엄청난 수행시간을 잡아먹고 있었다..
line 33~48 에서 좌표 (1, 1)을 먼저 Queue에 push하고 방문 체크를 한 후
while문으로 계속 돌려주었다. 나는 쓸데없이 이중 for문으로 O(n^2)의 시간을 잡아먹었는데..
일단 이 문제는 어찌되었건 (1, 1)은 무조건 도로일테고, 더이상 이동할 좌표가 없다면 절대 출발 좌표로
도달하지 못 할 것이니깐 굳이 이중 for문을 돌려가면서 모든 좌표를 탐색할 필요가 없었다.
잘 참고해야지..
line 33~34) 출발지점은 무조건 도로일테니까 Queue에 push해주고 방문 체크를 해준다.
line 35~48) 더이상 탐색할 좌표가 없을 때까지 반복
line 36~37) 이동할 좌표 정보를 Queue에서 꺼낸다.
line 39~47) 현재 좌표에서 상하좌우로 이동할 수 있는 좌표를 탐색한다.
line 40~41) 다음 좌표를 저장
line 42~46) 다음 좌표가 도로이고 미로의 범위를 벗어나지 않을 경우
line 42) 나는 미리 미로가 아닌 테두리는 모두 1로 초기화시켰었다.
여기서는 while문만 사용하기 위해 계속해서 좌표가 미로 범위 안에 포함되는지 확인해주어야 한다.
line 43~44) Queue에 해당 좌표를 push해주고, 방문 표시를 해준다.
line 45) 마찬가지로 출발 지점으로부터의 거리를 dis[][]에 저장.
출발~이전 도로까지의 거리 + 1
#. Result
- Input --------------------------------------------------------
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0
------------------------------------------------------------------
- Output --------------------------------------------------------
12
------------------------------------------------------------------
'PS > Problem_Solving' 카테고리의 다른 글
| [Inflearn] 라이언 킹 심바(BFS, priority_queue) (c/c++) (0) | 2020.05.14 |
|---|---|
| [Inflearn] 토마토(BFS) (c/c++) (0) | 2020.05.11 |
| [Inflearn] 섬나라 아일랜드(BFS) (0) | 2020.05.11 |
| [Inflearn] 피자 배달 거리(삼성 SW역량평가 기출 : DFS) (0) | 2020.05.09 |
| [Inflearn] 조합구하기(DFS) (c/c++) (0) | 2020.05.09 |