어흥
[백준 17090] 미로 탈출하기 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/17090
1. 주의할 점
- DFS를 통해 구현이 가능하지만, 메모라이즈 기법과 함께 사용하지 않으면 TLE가 발생한다
- 메모라이즈에 사용될 Visit배열을 -1로 초기화한다
2. 구현
- 모든 행과 열에 대해서 Visit배열의 값이 -1이 아니라면 DFS탐색을 시작한다
- DFS의 경우, 이미 방문한 적이 있다면(Visit값이 -1이 아닌경우) 해당 Visit배열의 값을 반환한다(메모라이즈 기법)
- 아직 방문한 적이 없다면, Visit갑을 0으로 넣고 해당 칸에 있는 문자에 대해 작업을 수행한다.
- 만약 이동하려는 곳이 범위 밖이라면 Visit값을 1로 바꾸고 Return 한다
#include <iostream>
using namespace std;
char arr[500][500];
int visit[500][500]; //-1: 방문 x, 0: 못나간다, 1: 나간다
int row, col, result = 0;
int dfs(int y, int x) {
if (visit[y][x] != -1) return visit[y][x]; //나가거나 나가지 못하는 경우
char c = arr[y][x];
int temp = 0;
visit[y][x] = 0;
if (c == 'U') {
if (y == 0) temp = 1;
else temp = dfs(y - 1, x);
}
else if (c == 'D') {
if (y == row - 1) temp = 1;
else temp = dfs(y + 1, x);
}
else if (c == 'L') {
if (x == 0) temp = 1;
else temp = dfs(y, x - 1);
}
else if (c == 'R') {
if (x == col - 1) temp = 1;
else temp = dfs(y, x + 1);
}
visit[y][x] = temp;
return temp;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> row >> col;
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
visit[i][j] = -1;
}
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
if (visit[i][j] == -1)
dfs(i, j);
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++)
if (visit[i][j] == 1)
result++;
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 6087] 레이저 통신 (C++) (0) | 2020.04.01 |
---|---|
[백준 4485] 녹색 옷 입은 애가 젤다지? (C++) (0) | 2020.03.31 |
[백준 11779] 최소비용 구하기 2 (C++) (0) | 2020.03.30 |
[백준 1916] 최소비용 구하기 (C++) (0) | 2020.03.30 |
[백준 14369] 전화번호 수수께끼 (Small,Large) (C++) (0) | 2020.03.30 |
Comments