728x90
반응형
1. 문제
https://www.acmicpc.net/problem/16724
2. 알고리즘 분류
- 자료 구조
- 그래프 이론
- 그래프 탐색
- 깊이 우선 탐색
- 분리 집합
3. 소스코드
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<char, pair<int, int>> dir;
int N, M;
char map[1003][1003];
// 해당 맵 포인트가 탐색이 되었는지 여부 확인
bool is_search(int y, int x)
{
if (map[y][x] == 0) return false; // 현재 지나가고 있는 길에 도착했을 경우, False 반환
else if (map[y][x] == 1) return true; // 이미 탐색이 완료된 길인 경우, True 반환
char val = map[y][x];
map[y][x] = 0; // 지나가고 있는 길 표시
bool ret = is_search(y + dir[val].first, x + dir[val].second); // 다음 지점으로 계속 이동
map[y][x] = 1; // 탐색 완료되었다는 표시
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// 알파벳에 따른 이동 방향 설정
dir['U'] = { -1, 0 };
dir['D'] = { 1, 0 };
dir['L'] = { 0, -1 };
dir['R'] = { 0, 1 };
// N : 지도의 행의 수, M : 지도의 열의 수 입력
cin >> N >> M;
// 지도의 정보 입력
for (int y = 0; y < N; y++)
for (int x = 0; x < M; x++)
cin >> map[y][x];
int cnt = 0;
// 모든 지점 탐색
for (int y = 0; y < N; y++)
for (int x = 0; x < M; x++)
if (!is_search(y, x)) cnt++; // 탐색이 되지않았다면 Count 1 증가
// 정답 출력
cout << cnt;
return 0;
}
4. 유용한 알고리즘
1) DFS(깊이 우선 탐색)
- 재귀로 들어가기 전에, map[y][x]에 0을 넣어주게 되면, 현재 DFS를 하면서 해당 좌표가 탐색 중이라는 것을 표기할 수 있다.
- 재귀로 들어가고 나온 후에, map[y][x]에 1을 넣어주게 되면, 탐색 다 끝나고 완료되었다는 것을 표기할 수 있다.
bool is_search(int y, int x)
{
if (map[y][x] == 0) return false; // 현재 지나가고 있는 길에 도착했을 경우, False 반환
else if (map[y][x] == 1) return true; // 이미 탐색이 완료된 길인 경우, True 반환
char val = map[y][x];
map[y][x] = 0; // 지나가고 있는 길 표시
bool ret = is_search(y + dir[val].first, x + dir[val].second); // 다음 지점으로 계속 이동
map[y][x] = 1; // 탐색 완료되었다는 표시
return ret;
}
728x90
'백준 알고리즘 > 백준 CLASS 5' 카테고리의 다른 글
[백준 C++] 1202번: 보석 도둑 (0) | 2024.04.06 |
---|---|
[백준 C++] 20303번: 할로윈의 양아치 (1) | 2024.04.03 |
[백준 C++] 11049번: 행렬 곱셈 순서 (0) | 2023.12.09 |
[백준 C++] 9466번: 텀 프로젝트 (1) | 2023.12.03 |
[백준 C++] 7579번: 앱 (0) | 2023.12.03 |