8월 3일 목요일 코테 : 알고리즘 강의 dfs

 

No. 1

 

 

-  문제 : DFS / 그래프 탐색

https://www.codetree.ai/missions/2/problems/graph-traversal?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드 

내가 짠 코드 1 .. count = 0 일때...  -1 또 안해주도록 장치 해놔야했음...

N,M = map(int,input().split())

# 그래프 생성 -> dfs 라서 인접리스트를 사용한다. 

graph=[[] for _ in range(N)]

for _ in range(M):
    x,y = map(int,input().split())
    
    x -=1
    y -=1

    graph[x].append(y)
    graph[y].append(x)

#print(graph)


#방문표시 
visited= [0 for _ in range(N)]




#dfs  함수 생성 
def dfs(vertex):
    for curr_v in graph[vertex]:
        if not visited[curr_v]:
            visited[curr_v] = 1 # 방문함으로 표시 
            dfs(curr_v) # 다시 탐색



#dfs 함수 호출 
dfs(0)


#최종개수 출력
count = sum(visited)
if count <= 0:
    print( count )
else:
    print(count-1)

 

답지풀이 1

일일이 세어줌.. 

# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))

#index를 1번 부터 사용하기 위해 m+1만큼 할당합니다.
graph = [[] for _ in range(n + 1)]

visited = [False for _ in range(n + 1)]
vertex_cnt = 0


def dfs(vertex):
    global vertex_cnt
    
    # 해당 정점에서 이어져있는 모든 정점을 탐색해줍니다.
    for curr_v in graph[vertex]:
        # 아직 간선이 존재하고 방문한 적이 없는 정점에 대해서만 탐색을 진행합니다.
        if not visited[curr_v]:
            visited[curr_v] = True
            vertex_cnt += 1
            dfs(curr_v)
    
    
for i in range(m):
    v1, v2 = tuple(map(int, input().split()))

    # 각 정점이 서로 이동이 가능한 양방향 그래프이기 때문에
    # 각 정점에 대한 간선을 각각 저장해줍니다.
    graph[v1].append(v2)
    graph[v2].append(v1)

visited[1] = True
dfs(1)

print(vertex_cnt)

 

 

강의듣고 다시 수정한 코드  -> count 값의 범위에따라 안나눠도됨. 

N,M = map(int,input().split())

# 그래프 생성 -> dfs 라서 인접리스트를 사용한다. 

graph=[[] for _ in range(N)]

for _ in range(M):
    x,y = map(int,input().split())
    
    x -=1
    y -=1

    graph[x].append(y)
    graph[y].append(x)

#print(graph)


#방문표시 
visited= [0 for _ in range(N)]




#dfs  함수 생성 
def dfs(vertex):
    visited[vertex] = 1 # 방문함으로 표시 
    for curr_v in graph[vertex]:
        if not visited[curr_v]:
            
            dfs(curr_v) # 다시 탐색



#dfs 함수 호출 
dfs(0)


#최종개수 출력
count = sum(visited)
print( count -1 )

"""count = sum(visited)
if count <= 0:
    print( count )
else:
    print(count-1)"""

 

 

새롭게 알게된것 

 

0번인덱스로 바꿀필요없이 그냥 첫째줄을 비워놓고 시작하면 숫자를 그대로 사용할수있다. 

 

visited를 True 로 만들어주는 위치 는 두가지 가능 

1. 함수 호출직전에 

2. 함수호출 내부에서 

 

 

주의할점

 

내가 짠 코드 .. count = 0 일때...  -1 또 안해주도록 장치 해놔야했음... 근데이게 첫번째 정점을 방문처리해주는 코드를 빼먹어서 그랬던듯 ㅠㅠ