Q. 3*3을 입력받아야 한다. 이 맵은 1과 0으로 이루어져있고, {0, 0}은 무조건 1임을 보장한다. {0, 0}부터 4방향을 기준으로 한칸씩 방문해나가며 방문한 정점은 다시 방문하지 않으며 방문하는 좌표를 출력하는 코드를 구현하시오. (0은 갈 수 없는 지역, 1은 갈 수 있는 지역을 뜻한다)
#include <iostream>
using namespace std;
const int N = 3;
int mp[N][N], visited[N][N];
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
void go(int y, int x) {
visited[y][x] = 1;
cout << y << ":" << x << "\n";
for(int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if(ny<0 || nx<0 || nx>=N || ny>=N) continue;
if(mp[ny][nx] == 0) continue;
if(visited[ny][nx]) continue;
go(ny, nx);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> mp[i][j];
}
}
go(0, 0);
}
해당 그래프를 DFS(깊이 우선 탐색)으로 방문하시오. 시작 노드는 1입니다.
#include <iostream>
#include <vector>
using namespace std;
const int n = 6;
vector<int> adj[n];
int visited[n];
void dfs(int u) {
visited[u] = 1;
cout << u << "\n";
for(int v : adj[u]) {
if(visited[v] == 0) { //방문하지 않았다면
dfs(v);
}
}
cout << u << "로부터 시작된 함수가 종료되었습니다.\n";
return;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
adj[1].push_back(2); adj[1].push_back(3);
adj[2].push_back(4); adj[2].push_back(5);
adj[4].push_back(2);
dfs(1); //1로부터 시작하는 dfs
}