1260번 DFS와 BFS

문제 출처 : https://www.acmicpc.net/problem/1260

---

1260번: DFS와 BFS

---

내가 제일 어려워하고 시도조차 하지 않(못)했던 BFS와 DFS,,,,,,,,

진짜 관련 문제 나올때마다 자연스럽게 쓰루~,,,,,,

ㅎㅎㅎ,, 근데 이젠 정말 정면돌파 해야할 것 같아서 블로그마다 개념을 다시 찾아보고 코드를 이해하려고 노력했다.

그래서 많은 코드와 방법 중 제일 이해가 잘 되었던 바로 아래의 코드..! 

내 방식대로 조금 변형했다.

문제에서 '입력으로 주어지는 간선은 양방향이다.' 라고 해서 line 4-7을 구현한 것이다.

또한, '단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.' 라고 되어있어서 바로 밑에 sort()를 구현했다.

dfs와 bfs는 아래 코드에 주석을 달아놓았다!

이를 이용해서 다른 기본적인 dfs와 bfs문제도 풀어봤는데 풀려서 너무너무너무 신기하고 감격스러웠다,,,,

앞으로 꾸준히 문제풀어야겠다..!

import sys
n,m,v=map(int, sys.stdin.readline().split())
a=[list() for i in range(n+1)]
for i in range(m):
    x,y=map(int, sys.stdin.readline().split())
    a[x].append(y)
    a[y].append(x)
for i in a:
    i.sort()
def dfs(node): #dfs
    chk[node]=True #bfs와 다르게 처음부터 False에서 True로
    print(node, end=" ")
    for next in a[node]: #다음 노드탐색
        if not chk[next]:
            dfs(next) #재귀호출해서 연결된 다음노드로
def bfs(w): #dfs
    global result
    q=[w] #import queue 대신 그냥 list로..!
    while q: 
        for i in range(len(q)):
            v=q.pop(0) #q의 제일 앞 원소를 빼온다.
            for j in range(len(a[v])):
                if not chk[a[v][j]]:
                    q.append(a[v][j]) #간선으로 연결된 정점들이 아직 방문되지 않았다면 추가
            if not chk[v]:
                chk[v]=True #q의 제일 앞 원소가 방문되지 않았다면 방문으로 바꿔줌
                result+=str(v)+" "
    return result
chk=[False]*(n+1)
dfs(v)
print()
result=""
chk=[False]*(n+1)
print(bfs(v))