[백준] 1260 - dfs와 bfs (미완-다시풀기)

n ,m, v = map(int, input().split())
#아래 한 줄이 핵심!! 아예 2차원 공간을 미리 구성해놓는다는 것!
grp = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    #어느 쪽이든 1 표시 (양방향이니까)
    grp[a][b]=grp[b][a]=1
#방문기록도 표시
visit = [0]*(n+1)

def dfs(V):
    visit[V]=1
    print(V, end=' ')
    for i in range(1, n+1):
        if visit[i]==0 and grp[V][i]==1:
            dfs(i)
        #여기서 for문 빠져나올 필요 없이, 쭉 돌리면 됨
        #어차피 숫자 작은 것부터 먼저 시행되게 돼있고 그래야 빠름

def bfs(V):
    #queue 라이브러리 안쓰고 리스트로 바로 저장 (리스트도 pop 쓸수 있으니까)
    queue=[V]
    #위에서 돌리고 1로 바뀌었으므로 이제 0으로 방문 표시
    visit[V]=0
    while queue: #이거 리스트도 가능??
        V=queue.pop(0) #리스트는 pop시에 위치 지정안하면 맨 뒤에꺼 빠짐
        print(V, end=' ')
        for i in range(1, n+1):
            if visit[i]==1 and grp[V][i]==1:
                que.append(i)
                visit[i]=0

dfs(v)
print()
bfs(v)

가나다라

• 풀이 결과 : 30분 이상 고민했으나, 느낌만 알고 코드로 못 풀어냄
• 풀이 과정 아이디어 : 아예 2차원 공간을 미리 구성해놓는다는 것! ⇒ grp = [[0]*(n+1) for i in range(n+1)]
• (또는 g = {i:[] for i in range(1, n+1)} 로 딕셔너리 사용 ⇒ {1:[ ], 2:[ ], 3:[ ]} )
• 위 방법으로 했더니 런타임에러가 났다...
• 이 문제처럼 노드 수는 많고, 연결선 수는 상대적으로 적은 경우엔, 위와 같은 인접행렬 말고 인접리스트가 적합하다고 함 (딕셔너리 또는 벡터 사용하는 것)
• "인접행렬 방법"은 모든 노드의 모든 연결여부를 확인해야 해서 시간 많이걸림
  ⇒ 특히, 희소그래프의 경우 메모리&시간 낭비 크다
• "인접리스트 방법"을 사용하면, 연결된 노드정보만 저장&확인해서 용량과 시간 아낄 수 있음⇒ 예를 들어, 특정 두 노드가 연결되어 있는지 확인하려고 한다면 grp[i]에서 j를 모두 돌아야 해서 시간 더 오래 걸릴 수도 있기 때문 : https://sarah950716.tistory.com/12
  ⇒ 이 문제에 인접리스트 적용한 풀이 : https://ebbnflow.tistory.com/173
  ⇒ 단, 밀집그래프에서는 인접행렬 방식이 더 적절할 수 있다.