[1260번] DFS와 BFS / python3 (feat.이코테 유튜브 강의)

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

1260번: DFS와 BFS

 

 

말그대로........... 이건 뭥미???? 😮

DFS.. BFS... 처음 보는 단어 등장

 

재택하는 남편님께 물어보니

깊이우선 탐색, 너비우선 탐색이라는 말을 꺼내기시작하는데.......

나의 공부 부족함을 바로 느끼고 유튜브에서 바로 강의를 찾아보기로 했다.

 

 

 

이렇게 샛길 공부를 마치고 난 뒤 스타투 START

샛길공부 링크: 1) https://coding-nurse.tistory.com/22

[샛길공부] DFS와 BFS (feat. 이코테 유튜브강의)

2) https://coding-nurse.tistory.com/26

[샛길공부] DFS와 BFS 문제풀기 (feat. 이코테 유튜브강의)

---

❌ 1~3차시도 실패

강의만 듣고 풀기에는 역시나 바로 적용해서 풀기에는 시간이 실수가 많았다.

맵 프레임을 그리고, 자료를 입력하는 것까진 수월하였으나 바로 적용해서 하기엔 무리데쓰😂

다른 분의 자료를 참고하여 나만의 식으로 풀기 시작하였다.

https://yoonsang-it.tistory.com/59

백준 1260번 파이썬 풀이: DFS와 BFS

---

❓ 정답은 ??

dfs와 bfs 두개를 구하는 만큼 역시나 길다~

# 정점번호 작은것부터 방문 
# 정점개수n, 사이 선개수m, 시작정점번호v
# 첫째줄 DFS 결과 방문순서
# 둘째줄 BFS 결과 방문순서
 
n,m,v=map(int,input().split())
graph=[[0]*(n+1) for _ in range(n+1)]   #맵 프레임 만들기
visit=[0] *(n+1)    #방문한 정점 체크 리스트
 
#맵 프레임에 자료 입력
for _ in range(m): 
    m1,m2=map(int,input().split())
    graph[m1][m2] = graph[m2][m1]=1
  
#dfs 깊이우선 탐색
def dfs(x):     #x부터 시작
    visit[x]=1      #방문한 정점은 1로 체크
    print(x,end=" ")     #방문한 정점 출력  
    for i in range(1,n+1):  
        # 조건: (방문하지 않아서 visit 리스트에 0으로 체크) 
        # and (맵에서 연결되어있다고 1이라고 표시되있는 경우)
        if visit[i]==0 and graph[x][i]==1:  
            dfs(i)  #계속 이어서 진행
 
 
#bfs 넓이우선 탐색
from collections import deque
 
def bfs(x):     #x부터 시작
    que=deque()
    que.append(x)     #연결된 정점넣을 리스트
    visit[x]=1      #방문한 정점은 1로 체크
 
    while que:
        x=que.popleft()     #왼쪽부터 꺼내기
        print(x,end=" ")     #방문한 정점 출력
        for i in range(1,n+1):
            #조건: (방문하지 않아서 리스트에 0으로 체크)
            #and (맵에서 연결되어있다고 1이라고 표시되있는 경우)
            if visit[i]==0 and graph[x][i]==1:
                que.append(i)   #조건만족하면 연결정점리스트에 넣기
                visit[i]=1      #그 다음 방문할 i정점에 방문했다고 1 표시
 
 
dfs(v)
print()     #줄바꿈하고
 
visit=[0]*(n+1) #다시 깨끗하게 리스트 만들고
bfs(v)

---

💯 풀이 과정

참고한 분의 bfs를 보면 큐형 자료 .popleft( )를 사용하기보다 .pop(0)으로 꺼내는 새로운 방법을 알게됨!

그래도 배운 것대로 해보자규⭐

주석처리로 나름 자세하게 적으면서 식을 적어내려봤다.

---

😎오늘의 한줄평: dfs, bfs 까먹기 전 더 비슷한 문제 풀어보기!