[백준] 2606번

백준 2606번

DFS/BFS

보고 나서 DFS,BFS 문제구나 했고 아직은 DFS가 편해서 dfs로 풀었다. 하지만 잘 못 풀었음

💗내 풀이💗

이 문제는 무방향 그래프이므로 data를 입력 받을때

a,b=map(int,input().split())
graph[a].append(b)
graph[b].append(a)

이렇게 해줘야한다. 그 전에 graph[[] for _ in range(N+1)]한다. 2차원 배열 만들어 줘야 한다.
그렇게 하고 나면
graph[1]=2,5
graph[2]=1,3,5
graph[3]=2
graph[4]=7
graph[5]=1,2,6
graph[6]=5
graph[7]=4 가 된다.

dfs함수는 cnt 변수가 있어야하므로 global로 선언한다. dfs에 들어갔다는건 방문한다는 의미이므로 visited[v]=1로 해준다. for문안에 if문을 둬서 만약 방문 하지 않았다면 dfs함수를 다시 적용해주고 cnt를 1 증가해준다.

💗내 코드💗

cnt=0
N=int(input())
T= int(input())
visited=[0]*(N+1)
graph=[[]for _ in range(N+1)]

def dfs(v):
    global cnt
    visited[v]=1
    for i in graph[v]:
        if visited[i]==0:
            dfs(i)
            cnt+=1
    
for _ in range(T):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
dfs(1)
print(cnt)