💡 백트래킹/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 2020KB Time 544ms Code Length 813B
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
#include<iostream>
int R, C;
char map[20][21];
int visited[255];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
int max = 0;
void dfs(int y, int x, int cnt) {
int way = 4;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= R || nx >= C || ny < 0 || nx < 0 || visited[map[ny][nx]]) way--;
}
if (way == 0) {
if (max < cnt) {
max = cnt;
}
return;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= R || nx >= C || ny < 0 || nx < 0) continue;
if (visited[map[ny][nx]]) continue;
visited[map[ny][nx]] = 1;
dfs(ny, nx, cnt + 1);
visited[map[ny][nx]] = 0;
}
}
int main() {
scanf("%d %d", &R, &C);
for (int i = 0; i < R; i++) {
scanf(" %s", &map[i]);
}
visited[map[0][0]] = 1;
dfs(0,0, 1);
printf("%d\n", max);
}
이 코드는 입력으로 받은 지도에서 상하좌우로 이동하면서 최대한 많은 칸을 방문하는 DFS(깊이 우선 탐색) 알고리즘을 구현한 것이다.
- 먼저 입력으로 받은 지도의 크기와 내용을 저장한다.
- 방문한 칸을 체크하기 위한 visited 배열을 초기화한다.
- 상하좌우로 이동하는 방향을 나타내는 dy, dx 배열을 설정한다.
- dfs 함수는 현재 위치와 방문한 칸의 수를 인자로 받는다.
- 주어진 위치에서 상하좌우로 이동할 수 있는지 확인하고, 이동할 수 있는 방향의 수를 계산한다.
- 만약 이동할 수 있는 방향이 없다면, 현재까지 방문한 칸의 수를 최대값과 비교하여 갱신한다.
- 이동할 수 있는 방향이 있다면, 각 방향으로 이동하고 해당 칸을 방문했음을 표시한 뒤, 재귀적으로 dfs 함수를 호출한다.
- 모든 경우의 수를 탐색한 후, 최대 방문 칸 수를 출력한다.
