[Python] 1260번 DFS와 BFS

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

 

코테 준비하면서 오랜만에 다시 보게 된 DFS와 BFS

 

DFS를 풀 때는 재귀함수를 통해서, BFS를 풀 때는 queue를 통해서 풀었다.

def bfs(qu,visited):
    while qu:
        q=qu.pop(0)
        if visited[q]==True:
            pass
        else:
            print(q,end=' ')
            visited[q]=True
            for i in range(n+1):
                if matrix[q][i]==1 and visited[i]==False:
                    qu.append(i)
                    
n,m,v=map(int,input().split()) #n:정점수,m:간선수,v:시작정점
matrix=[[0]*(n+1) for _ in range(n+1)]

for _ in range(m):
    v1,v2=map(int,input().split())
    matrix[v1][v2]=1
    matrix[v2][v1]=1
    

visited_dfs = [False for _ in range(n + 1)]  # DFS용 방문 체크
visited_bfs = [False for _ in range(n + 1)]  # BFS용 방문 체크

bfs([v],visited)

 

여기서 마지막에 원래는 visited를 하나만 했지만 하나만 하니까 dfs()와 bfs()에서 visited 리스트를 공유하는 문제가 생겼다. 이전에 똑같이 생겼던 shallow copy의 문제였다. 그래서 visited를 각각 따로 만들어주었다.