[2022.12.01]

베뉴·2022년 12월 1일
0

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
}
profile
백문이불여일타(이전 블로그: https://blog.naver.com/christer10)

0개의 댓글