1. 활동 내역

• 알고리즘 문제 해결 전략 공부 및 문제풀이
• python 복습

1) 알고리즘 문제해결(dfs)

DFS는 그래프 탐색 알고리즘 중 하나로, 이름 그대로 "깊이 우선"으로 그래프를 탐색하는 방법입니다.

그래프? 그래프는 노드(정점)와 이들을 연결하는 간선으로 이루어진 자료구조입니다. DFS는 한 노드에서 시작해 다음 노드로 이동할 때, 갈 수 있는 가장 깊은 곳까지 이동한 후, 더 이상 이동할 곳이 없으면 다시 이전 노드로 돌아오면서 탐색을 계속하는 방식이다.

DFS 동작 원리

1. 시작 노드 선택: 탐색을 시작할 노드를 선택
2. 방문 처리: 현재 노드를 방문 처리(방문 여부를 기록)하고, 방문한 노드에서 갈 수 있는 인접 노드를 탐색
3. 재귀적 탐색: 방문하지 않은 인접 노드가 있다면, 그 노드를 새로운 시작 노드로 삼아 탐색
4. 백트래킹: 더 이상 방문할 인접 노드가 없다면, 이전 노드로 되돌아가서 다른 인접 노드를 탐색
5. 종료: 모든 노드를 방문했거나 더 이상 탐색할 노드가 없으면, DFS 탐색을 종료

// 해결한 문제: 바이러스
#include <stdio.h>

int graph[101][101];
int dfsv[101];
int result = 0;

void dfs(int v, int n)
{
    dfsv[v]=1;
    
    for (size_t i = 1; i <= n; i++)
    {
        if(graph[v][i] == 1 && dfsv[i]==0)
        {
            result++;
            dfs(i,n);
        }
    }
    return;
}

int main(void)
{
    int com, line;
    scanf("%d\\n%d",&com,&line);
    for (size_t i = 0; i < line; i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        graph[x][y] = 1;
        graph[y][x] = 1;
    }
    dfs(1,com);
    printf("%d",result);
    
}

• 그래프 초기화
  • graph[101][101] 배열은 최대 100대의 컴퓨터까지 고려해 크기를 101로 설정하고 두 정점간의 연결 상태를 2차원 배열의 첫번째 두번째 인덱스에 기록
  • dfsv[101] 배열은 각 컴퓨터의 방문 여부를 기록한다. 방문 안한 노드는 0, 방문한 노드는 1로 설정
• DFS 함수
  • 특정 컴퓨터(정점)를 방문 처리한 후, 그 컴퓨터와 연결된 모든 컴퓨터를 재귀적으로 탐색.
  • graph[v][i] == 1 && dfsv[i]==0 를 이용해 이미 방문한 컴퓨터는 다시 탐색하지 않고, 방문하지 않은 컴퓨터만 탐색
• 메인 함수:
  • 컴퓨터의 수와 연결된 간선의 수를 입력받고, 이를 기반으로 그래프를 만듬
  • 1번 컴퓨터를 시작점으로 DFS를 호출해 바이러스가 퍼질 수 있는 모든 컴퓨터를 탐색
  • 최종적으로 바이러스에 감염된 컴퓨터의 수를 출력

2) python복습(객체지향)

• 객체지향 프로그래밍 데이터를 객체로 처리하고, 객체 간의 상호작용을 통해 프로그램을 설계하는 방법

1. 클래스 정의

클래스는 class 키워드를 사용해 정의한다. 클래스에는 속성(데이터)과 메서드(함수)가 포함될 수 있다. 속성은 객체의 상태를 나타내며, 메서드는 객체의 행동을 정의한다.