알고리즘 문제풀이📝 DFS(1)

백준 2606번 바이러스

https://www.acmicpc.net/problem/2606

🌙 방법

1. 연결되는 것들끼리 묶어서 배열을 만든다
   만들어진 배열을 토대로 이어진 형태를 모두 표시하는 그래프를 만든다
   숫자와 관계없이 연결된 것을 모두 표현하기 위해 반복문을 한번 더 돌린다

2. start_node를 담은 stack과 방문경험을 나타내는 visited 배열 생성한다
   current_node는 stack에서 값을 뽑아서 사용하고 바로 visited에 추가해준다

3. 반복문을 사용하여 그래프에 current_node의 value들을 검사해서
   visited에도 없고 stack에도 없어야 stack에 append, 아니라면 pass한다
   visited에 들어있는 배열에서 1번 컴퓨터를 제외한 값을 출력한다

4. stack에 아무런 값도 들어있지 않은 경우에 반복문을 멈춘다

computers = int(input())
pairs = int(input())

two_coms=[]
for i in range(pairs):
    connect = list(map(int,input().split()))
    two_coms.append(connect)                    # [[1,2],[2,3]...]

graph={}
for i in range(1,computer_num+1):                
    graph[i]=[]     
    for j in range(pairs):                               
        if i == two_coms[j][0]:                    
            graph[i].append(two_coms[j][1])
        if i == two_coms[j][1]:                    
            graph[i].append(two_coms[j][0])   

# {1: [2, 5], 2: [3, 5], 3: [], 4: [7], 5: [6], 6: [], 7: []}
# {1: [2, 5], 2: [1, 3, 5], 3: [2], 4: [7], 5: [1, 2, 6], 6: [5], 7: [4]}


def dfs_stack(graph,start_node):
    stack=[start_node]                                   
    visited=[]                                             
                                                       
    while stack:
        current_node =stack.pop()   
        visited.append(current_node)      
        
        for com_node in graph[current_node]:         
            if (com_node not in visited) and (com_node not in stack):                 
                stack.append(com_node)  
            else:
                pass
    print(len(visited)-1)

 

dfs_stack(graph,1)