[알고리즘/BFS & DFS] 1260번 : DFS와 BFS - python

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

1260번: DFS와 BFS

 

---

• 문제
• 소요시간: 연습

---

• 설계하기(접근방법) 

1. 입력받기

정점, 간선, 시작 정점을 입력받는다

 

2. 구현하기

dfs와 bfs를 각각 구현한다

2번에 걸쳐서 돌릴 것이기 때문에

각각 visited를 선언해준다

 

또한 입력 조건에 간선을 순서대로 준다는 말이 없고

정점을 작은 순서대로 방문한다고 했으니

 

for i in graph:

i.sort()를 통해

정렬해준다

 

dfs의 경우

visited가 False인 경우

dfs()를 실행한다

 

bfs의 경우

q를 선언하고

q를 v =  popleft() 하여

그 v에 대한 그래프 정보들을, visited가 False인 경우 전부 탐색한다

True로 바꿔준 후 q에 append 해준다

 

3. 출력하기

dfs bfs 함수내에서 

방문할 때마다 출력해준다

 

 

---

• 코드(출력)

from collections import deque

def dfs(v):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if visited[i] == False:
            dfs(i)


def bfs(v) :
    q = deque()
    q.append(v)
    visited[v] = True
    while q:
        v = q.popleft() # v = 1
        print(v, end = " ")
        for i in graph[v]:
            if visited[i] == False:
                visited[i] = True
                q.append(i)

n, m, v = map(int, input().split())

graph = [[] for _ in range(n + 1)]


for _ in range(m):
    a ,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

## dfs
visited = [False] * (n + 1)
dfs(v)
print()
## bfs
visited = [False] * (n + 1)
bfs(v)

---

• 얻어갈 부분

1. 이번에는 0이 아닌 True, False로 visited를 구현했다. True, False에 익숙하지 않아 논리연산자를 대입하지 않고 자꾸 비교연산자를 사용해 코드에 에러가 발생했다

visited[v] = True로 해야하는데

visited[v] == True로 했다

차라리 0,1로 통일하여 방지하자

2. q에 append할 때 visited[i]를 append 해야하는데 자꾸

q.append(visited[i])로 배열을 append 했다

for문 내에서 visited i 가 돌고 있으니 이 점을 유의하자