반응형
https://www.acmicpc.net/problem/17090
17090번: 미로 탈출하기
크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문
www.acmicpc.net
[ 문제풀이 ]
1. visited [ 501 ][ 501 ] 배열을 만들어서 -1로 초기화합니다.
2. dfs를 통해 해당 좌표에 방문 시 visited배열이 -1이 아니라면 그 값을 return 합니다.
3. visited 배열을 0으로 초기화시키고, 지도에 적힌 문자대로 이동합니다.
4. 이동했을 때 지도 밖으로 나간다면 1을 return 하고, 그렇지 않다면 다시 재귀해 줍니다.
5. visited 배열에서 값이 1인 칸의 개수를 출력합니다.
[ 소스코드 ]
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 | #include<iostream> #include<cstring> using namespace std; int N, M; char arr[501][501]; int visited[505][505]; int dfs(int r, int c) { if (visited[r][c] != -1) return visited[r][c]; visited[r][c] = 0; if (arr[r][c] == 'U') { if (r == 0) return visited[r][c] = 1; else return visited[r][c] = dfs(r - 1, c); } else if (arr[r][c] == 'R') { if (c == M-1) return visited[r][c] = 1; else return visited[r][c] = dfs(r, c + 1); } else if (arr[r][c] == 'D') { if (r == N - 1) return visited[r][c] = 1; else return visited[r][c] = dfs(r + 1, c); } else { if (c == 0) return visited[r][c] = 1; else return visited[r][c] = dfs(r, c - 1); } } int main() { scanf("%d %d", &N, &M); memset(visited, -1, sizeof(visited)); for (int i = 0; i < N; i++) { scanf("%s", &arr[i]); } int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (visited[i][j] == -1) { if (dfs(i, j)) ans++; } else if (visited[i][j] == 1) ans++; } } printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 13418번 - 학교 탐방하기 (C++) (0) | 2023.01.29 |
|---|---|
| [ 백준 ] 16398번 - 행성 연결 (C++) (0) | 2023.01.28 |
| [ 백준 ] 14923번 - 미로 탈출 (C++) (0) | 2023.01.26 |
| [ 백준 ] 5558번 - チーズ (Cheese) (C++) (0) | 2023.01.25 |
| [ 백준 ] 3770번 - 대한민국 (C++) (0) | 2023.01.24 |